c++ - 如何跟踪整数变化 vector 的中位数？

Question

试图在 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

Answer 1

一种简单的方法是维护两个已排序的容器，一个比中位数低，一个比中位数大。

当你找到一个新元素时，看看将它插入到哪个容器中(这样 lower 的所有元素总是小于或等于 upper 的所有元素)，然后重新平衡计数，使中位数“在间隙中”他们之间。

你的有点像这样做，但将下限定义为 [.begin(), it)上面是[it, .end()) .除非性能特别重要，否则我会让它们成为单独的容器，以减少您需要在头脑中保持理解代码的状态量。

维护两个已排序的容器，low和 high ，具有以下不变量:

• low.size()与high.size()相同或 1 个更大的
• low 的每个元素小于或等于 high 的每个元素.那么low的中位数 union high是low.last() .

假设你有这么一对容器，如果你想添加一个元素x ，我会首先维护不变量 2——如果 low.empty()或 x <= low.last() , 把它贴在 low , 否则将其粘贴在 high 中.

接下来，保持不变量1:if high元素多于 low，从 high 中移除最低元素并将其添加到 low .如果low比 high 多 2 个元素, 从 low 中移除最高元素并将其添加到 high .

如果我们从 low 开始和 high服从上述两个不变量，那么在上述步骤之后我们仍然有一个 low和 high服从这两个不变量。当以上两个不变量成立时，中位数为low.last() !