4

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

3 回答 3

7

一个简单的方法是维护两个分类容器，一个低于中间值，一个大于中间值。

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

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

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

  • low.size()等于high.size()或大 1
  • 的每个元素low都小于或等于 的每个元素high。那么并low集的中位数high是low.last()。

假设你有这样一对容器，如果你想添加一个元素x，我会首先保持不变量 2——如果low.empty()或x <= low.last()，则将其插入，low否则将其插入high。

接下来，保持不变量 1：如果high元素多于 low，则从 中删除最低元素high并将其添加到low. 如果low有 2 个以上的元素high，则从 中删除最高元素low并将其添加到high.

如果我们从 a lowand highthat 开始，它服从上述两个不变量，那么经过上述步骤，我们仍然有 a lowand highthat 服从这两个不变量。当上述两个不变量成立时，中位数为low.last()！

于 2013-10-04T18:12:32.837 回答
3

您似乎正在尝试做的事情（错误地，使用您发布的代码）是将值保留在具有指向中值的迭代器的多重集中，并在每次添加到集合时根据您的值是否是调整该指针加法高于或低于中位数。

这是一个很好的设计，可能是解决这个问题的最快方法。但是，它无法使用，std::multiset因为它会std::multiset导致一个关键极端情况出现问题——当添加到集合中的新值等于旧中值时，您无法知道它是否之前被插入或在多重集中的旧中位数之后。所以在这种情况下你不知道如何调整中值指针。

因此，如果您想以这种方式解决问题，您需要实现自己的 rbtree 或其他集合抽象，以便为您提供这一关键信息。或者，当插入一个等于旧中位数的值时，您可以从头开始重新查找中位数（这是一项昂贵的操作，但应该很少见）。

编辑

OP 使代码与 C++11 多集一起工作的提示：

  • 您需要itr在将第一个值插入多重集中时进行初始化

  • 您只需要itr在插入到“错误”的一侧后进行调整itr。您可以根据多重集大小是奇数还是偶数来判断哪一边是“错误的”。

  • 因为在您不itr希望测试之后，总是会插入一个等于旧中位数的值
    if (k < *itr)<=

于 2013-10-04T19:02:35.753 回答
1

只使用一个std::vector怎么样？通过插入std::lower_bound告诉您的位置来保持值排序。

    std::vector<int> p;
    int k, med_sum;
    while(cin >> k)
    {
      p.insert(std::lower_bound(p.begin(), p.end(), k), k);
      med_sum += p[p.size()/2];
    }
    std::cout << med_sum << std::endl;

编辑
使用向量的优点是算法非常清晰和简洁（只有 3 行逻辑），并且内存的缓存局部性vector和大容量内存分配使其至少与map/set或list实现相比具有竞争力，即使它的插入是O(n).

为了比较，我使用以下代码编写了一个（未经测试的）实现multiset：

    std::multiset<int> p;
    int k, med_sum;
    cin >> med_sum;
    p.insert(med_sum);
    std::multiset<int>::iterator itr = p.begin();
    while(cin >> k)
    {
      if(p.size() % 2 == 0)
      {
         if(k < *itr) ++itr;
      }
      else
      {
         if(k < *itr) --itr;
         else ++itr;
      }
      med_sum += *itr;
    }
    cout << med_sum << endl;

7 行逻辑还不错，但肯定不太清楚发生了什么，我无法仅通过查看它来判断它是否正确。请注意，此算法仅适用于C++11在multimap::insert范围（重复项）的顶端插入重复值的情况。

总而言之，我认为vector实施是更好的方法，除非必要性和测量结果表明要与multiset

于 2013-10-04T19:15:55.117 回答