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

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;

EDIT
ベクトルを使用する利点は、アルゴリズムが非常に明確で簡潔であり（ロジックの3行のみ）、メモリのキャッシュ局所性とバルクメモリ割り当てにより、 /または実装に対してvector少なくとも競争力があることですその挿入は。 mapsetlistO(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 に答える