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

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

問題へのリンク

問題概要

個の整数 が与えられる。 は偶数である。次の条件を満たすような整数 が何通りあるかを求めよ。

• のうち、 以上の整数が 個である
• のうち、 未満の整数が 個である

制約

• 
• は偶数

考えたこと

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

そして、ソートしてみると、もう割とすぐに答えが見える。例えば とすると

• のとき、 と ) に分かれる

ということがわかる。 だとギリギリダメで と になってしまうのでダメ。

整理

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

• の 番目の値から
• の 番目の値を引く

とすればよいのだ。

#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;
}