けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 132 C - Divide the Problems (300 点)

ソートして頑張る。
ソートすればいいと思い至りさえすれば、結構ソートするだけに近い感じの雰囲気の問題で、一瞬罠があるのかなと怖くなった。

問題へのリンク

問題概要

 N 個の整数  d_1, d_2, \dots, d_N が与えられる。 N は偶数である。次の条件を満たすような整数  K が何通りあるかを求めよ。

  •  d_1, d_2, \dots, d_N のうち、 K 以上の整数が  \frac{N}{2} 個である
  •  d_1, d_2, \dots, d_N のうち、 K 未満の整数が  \frac{N}{2} 個である

制約

  •  2 \le N \le 10^{5}
  •  N は偶数

考えたこと

とりあえず  d は小さい順にソートしてしまって OK!!!
こういう風に、数列の順序が特に問題と関係ない場合にはとりあえずソートするというのは是非やっておくべきことではある。

そして、ソートしてみると、もう割とすぐに答えが見える。例えば  d = (1, 4, 7, 10, 13, 15) とすると

  •  K = 8, 9, 10 のとき、 (1, 4, 7) (10, 13, 15) に分かれる

ということがわかる。 K = 7 だとギリギリダメで  (1, 4) (7, 10, 13, 15) になってしまうのでダメ。

整理

この状況をすばやく整理することが求められる。ようするに

  •  d \frac{N}{2} 番目の値から
  •  d \frac{N}{2} - 1 番目の値を引く

とすればよいのだ。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> d(N);
    for (int i = 0; i < N; ++i) cin >> d[i];

    sort(d.begin(), d.end());
    long long left = d[N/2-1];
    long long right = d[N/2];
    cout << right - left << endl;
}