试图在http://www.hackerearth.com/problem/algorithm/sum-of-medians-1/上解决一个问题,并考虑使用多重集来解决它,因为它可能包含重复的值。我尝试编码如下:
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
int n,k,med_sum=0,p;
cin>>n;
multiset<int> m;
multiset<int>::iterator itr;
for(int i=0;i<n;i++)
{
cin>>k;
m.insert(k);
p=k;
if(p<=k)
itr--;
else
itr++;
med_sum+=*itr;
}
cout<<med_sum<<endl;
return 0;
}
Sample Input:
n=5
10
5
1
2
15
Sample Output: 27
Explanation:
m(1)=median of [10]=10
m(2)=median of [10 5]=5
m(3)=median of [10 5 1]=5
m(4)=median of [10 5 1 2 15]=5
med_sum=10+5+5+2+5=27