#include <bits/stdc++.h>
using namespace std;
class SpecialAverage {
public:
multiset<int> left, mid, right;
int n, k;
long pos, sum;
vector<int> v;
SpecialAverage(int nvalue, int kvalue)
{
n = nvalue;
k = kvalue;
pos = 0;
sum = 0;
for (int i = 0; i < n; i++)
v.push_back(0);
}
void add(int num)
{
left.insert(num);
if (left.size() > k) {
int temp = *(prev(end(left)));
mid.insert(temp);
left.erase(prev(end(left)));
sum += temp;
}
if (mid.size() > (n - 2 * k)) {
int temp = *(prev(end(mid)));
right.insert(temp);
mid.erase(prev(end(mid)));
sum -= temp;
}
}
void remove(int ele)
{
if (ele <= *(left.rbegin()))
left.erase(left.find(ele));
else if (ele <= *(mid.rbegin())) {
sum -= ele;
mid.erase(mid.find(ele));
}
else
right.erase(right.find(ele));
if (left.size() < k) {
int temp = *(mid.begin());
left.insert(temp);
mid.erase(mid.begin());
sum -= temp;
}
if (mid.size() < (n - 2 * k)) {
int temp = *(right.begin());
mid.insert(temp);
right.erase(right.begin());
sum += temp;
}
}
void addInteger(int num)
{
if (pos >= n)
remove(v[pos % n]);
v[(pos++) % n] = num;
add(num);
}
int calculateSpecialAverage()
{
if (pos >= n)
return ((double)sum) / (n - 2 * k);
return -1;
}
};
void processQueries(int n, int k)
{
SpecialAverage* avg
= new SpecialAverage(n, k);
avg->addInteger(4);
avg->addInteger(2);
cout << avg->calculateSpecialAverage()
<< endl;
avg->addInteger(10);
cout << avg->calculateSpecialAverage()
<< endl;
}
int main()
{
int N = 3, K = 1;
processQueries(N, K);
return 0;
}
Original page link
Best Cool Tech Gadgets
Top favorite technology gadgets
0 comments:
Post a Comment