POJ 3784 - Running Median

http://poj.org/problem?id=3784

概要

M 個の数列が与えられるので，各奇数番目の数が読まれた時点での中央値を答える．

制約

• 数列の要素は符号付き 32bit 整数値
• 1 <= M <= 9999, M は奇数

解法

M 個すべて読んでからソートし，後から追加されたものを取り除きながら中央値を逆から求める．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int T;
 9   scanf("%d", &T);
10   while (T-- > 0) {
11     int id, M;
12     scanf("%d %d", &id, &M);
13     vector<int> v(M);
14     for (int i = 0; i < M; i++) {
15       scanf("%d", &v[i]);
16     }
17     const vector<int> w = v;
18     sort(v.begin(), v.end());
19 
20     vector<int> ans((M+1)/2);
21     ans[(M-1)/2] = v[(M-1)/2];
22     for (int i = M-1; i > 0; i -= 2) {
23       vector<int>::iterator it = lower_bound(v.begin(), v.end(), w[i]);
24       v.erase(it);
25       it = lower_bound(v.begin(), v.end(), w[i-1]);
26       v.erase(it);
27       ans[(i-1)/2] = v[(i-1)/2];
28     }
29 
30     printf("%d %d", id, (M+1)/2);
31     for (int i = 0; i <= (M-1)/2; i++) {
32       if (i % 10 == 0) {
33         printf("\n%d", ans[i]);
34       } else {
35         printf(" %d", ans[i]);
36       }
37     }
38     putchar('\n');
39   }
40   return 0;
41 }