#include <iostream>
using namespace std;
#include <vector>
#include <queue>
#include <unordered_map>
std::vector<double> findMeanForLastNElementsExcludingTopK(const std::vector<int>& arr, int lastN, int k) {
if (lastN <= k || arr.empty()) {
return {}; // Return empty vector for invalid input
}
int sum_n = 0, sum_k = 0;
std::vector<double> result;
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
std::unordered_map<int, int> to_remove;
// Process first window of size lastN
for (int i = 0; i < lastN; ++i) {
sum_n += arr[i];
if (pq.size() < k) {
sum_k += arr[i];
pq.push(arr[i]);
} else if (arr[i] > pq.top()) {
sum_k += arr[i] - pq.top();
pq.pop();
pq.push(arr[i]);
}
}
result.push_back(static_cast<double>(sum_n - sum_k) / (lastN - k));
// Process rest of the stream
for (size_t i = lastN; i < arr.size(); ++i) {
// Remove oldest element from the window
int oldest = arr[i - lastN];
sum_n += arr[i] - oldest;
if (oldest >= pq.top()) {
sum_k -= oldest;
to_remove[oldest]++;
}
// Add new element
if (pq.size() < k) {
pq.push(arr[i]);
sum_k += arr[i];
} else if (arr[i] > pq.top()) {
sum_k += arr[i] - pq.top();
pq.pop();
pq.push(arr[i]);
}
// Remove elements from priority queue that are no longer in the window
while (!pq.empty() && to_remove.count(pq.top())) {
if (--to_remove[pq.top()] == 0) {
to_remove.erase(pq.top());
}
pq.pop();
}
result.push_back(static_cast<double>(sum_n - sum_k) / (lastN - k));
}
return result;
}
int main() {
// your code goes here
vector<int> input = {20, 2, -2, 0, 10, 1, 5, -2, 0};
vector<double> ans = findMeanForLastNElementsExcludingTopK(input, 5,2);
for(auto x: ans) {
cout<<x<<" ";
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KCnN0ZDo6dmVjdG9yPGRvdWJsZT4gZmluZE1lYW5Gb3JMYXN0TkVsZW1lbnRzRXhjbHVkaW5nVG9wSyhjb25zdCBzdGQ6OnZlY3RvcjxpbnQ+JiBhcnIsIGludCBsYXN0TiwgaW50IGspIHsKICAgIGlmIChsYXN0TiA8PSBrIHx8IGFyci5lbXB0eSgpKSB7CiAgICAgICAgcmV0dXJuIHt9OyAgLy8gUmV0dXJuIGVtcHR5IHZlY3RvciBmb3IgaW52YWxpZCBpbnB1dAogICAgfQoKICAgIGludCBzdW1fbiA9IDAsIHN1bV9rID0gMDsKICAgIHN0ZDo6dmVjdG9yPGRvdWJsZT4gcmVzdWx0OwogICAgc3RkOjpwcmlvcml0eV9xdWV1ZTxpbnQsIHN0ZDo6dmVjdG9yPGludD4sIHN0ZDo6Z3JlYXRlcjxpbnQ+PiBwcTsKICAgIHN0ZDo6dW5vcmRlcmVkX21hcDxpbnQsIGludD4gdG9fcmVtb3ZlOwoKICAgIC8vIFByb2Nlc3MgZmlyc3Qgd2luZG93IG9mIHNpemUgbGFzdE4KICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbGFzdE47ICsraSkgewogICAgICAgIHN1bV9uICs9IGFycltpXTsKICAgICAgICBpZiAocHEuc2l6ZSgpIDwgaykgewogICAgICAgICAgICBzdW1fayArPSBhcnJbaV07CiAgICAgICAgICAgIHBxLnB1c2goYXJyW2ldKTsKICAgICAgICB9IGVsc2UgaWYgKGFycltpXSA+IHBxLnRvcCgpKSB7CiAgICAgICAgICAgIHN1bV9rICs9IGFycltpXSAtIHBxLnRvcCgpOwogICAgICAgICAgICBwcS5wb3AoKTsKICAgICAgICAgICAgcHEucHVzaChhcnJbaV0pOwogICAgICAgIH0KICAgIH0KCiAgICByZXN1bHQucHVzaF9iYWNrKHN0YXRpY19jYXN0PGRvdWJsZT4oc3VtX24gLSBzdW1faykgLyAobGFzdE4gLSBrKSk7CgogICAgLy8gUHJvY2VzcyByZXN0IG9mIHRoZSBzdHJlYW0KICAgIGZvciAoc2l6ZV90IGkgPSBsYXN0TjsgaSA8IGFyci5zaXplKCk7ICsraSkgewogICAgICAgIC8vIFJlbW92ZSBvbGRlc3QgZWxlbWVudCBmcm9tIHRoZSB3aW5kb3cKICAgICAgICBpbnQgb2xkZXN0ID0gYXJyW2kgLSBsYXN0Tl07CiAgICAgICAgc3VtX24gKz0gYXJyW2ldIC0gb2xkZXN0OwoKICAgICAgICBpZiAob2xkZXN0ID49IHBxLnRvcCgpKSB7CiAgICAgICAgICAgIHN1bV9rIC09IG9sZGVzdDsKICAgICAgICAgICAgdG9fcmVtb3ZlW29sZGVzdF0rKzsKICAgICAgICB9CgogICAgICAgIC8vIEFkZCBuZXcgZWxlbWVudAogICAgICAgIGlmIChwcS5zaXplKCkgPCBrKSB7CiAgICAgICAgICAgIHBxLnB1c2goYXJyW2ldKTsKICAgICAgICAgICAgc3VtX2sgKz0gYXJyW2ldOwogICAgICAgIH0gZWxzZSBpZiAoYXJyW2ldID4gcHEudG9wKCkpIHsKICAgICAgICAgICAgc3VtX2sgKz0gYXJyW2ldIC0gcHEudG9wKCk7CiAgICAgICAgICAgIHBxLnBvcCgpOwogICAgICAgICAgICBwcS5wdXNoKGFycltpXSk7CiAgICAgICAgfQoKICAgICAgICAvLyBSZW1vdmUgZWxlbWVudHMgZnJvbSBwcmlvcml0eSBxdWV1ZSB0aGF0IGFyZSBubyBsb25nZXIgaW4gdGhlIHdpbmRvdwogICAgICAgIHdoaWxlICghcHEuZW1wdHkoKSAmJiB0b19yZW1vdmUuY291bnQocHEudG9wKCkpKSB7CiAgICAgICAgICAgIGlmICgtLXRvX3JlbW92ZVtwcS50b3AoKV0gPT0gMCkgewogICAgICAgICAgICAgICAgdG9fcmVtb3ZlLmVyYXNlKHBxLnRvcCgpKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBwcS5wb3AoKTsKICAgICAgICB9CgogICAgICAgIHJlc3VsdC5wdXNoX2JhY2soc3RhdGljX2Nhc3Q8ZG91YmxlPihzdW1fbiAtIHN1bV9rKSAvIChsYXN0TiAtIGspKTsKICAgIH0KCiAgICByZXR1cm4gcmVzdWx0Owp9CgppbnQgbWFpbigpIHsKCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCQoJdmVjdG9yPGludD4gaW5wdXQgPSB7MjAsIDIsIC0yLCAwLCAxMCwgMSwgNSwgLTIsIDB9OwoJdmVjdG9yPGRvdWJsZT4gYW5zID0gZmluZE1lYW5Gb3JMYXN0TkVsZW1lbnRzRXhjbHVkaW5nVG9wSyhpbnB1dCwgNSwyKTsKCQoJZm9yKGF1dG8geDogYW5zKSB7CgkJY291dDw8eDw8IiAiOwoJfQoJCglyZXR1cm4gMDsKfQ==