POJ 2623 - Sequence Median

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

概要

N 個の非負整数が与えられるので，それの中央値を答える．

N が奇数のときは，ソート後の数列の (N+1)/2 番目の値が中央値であり，N が偶数のときはソート後の数列の N/2 番目の値と N/2+1 番目の値の平均が中央値である．

制約

• 1 <= N <= 250000
• 0 < 数列の要素の値 <= 2^32 - 1
• 出力は 10^-1 の精度

解法

やるだけ．N が奇数のときも小数点以下を出力する必要があることに注意…

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main(void)
 7 {
 8   int n;
 9   scanf("%d", &n);
10   vector<int> seq(n);
11   for (int i = 0; i < n; i++) {
12     scanf("%d", &seq[i]);
13   }
14   sort(seq.begin(), seq.end());
15   if (n % 2  == 0) {
16     printf("%.1f\n", (double(seq[(n-1)/2]) + seq[(n+1)/2]) / 2.0);
17   } else {
18     printf("%.1f\n", double(seq[n/2]));
19   }
20   return 0;
21 }