ソートして頑張る。
ソートすればいいと思い至りさえすれば、結構ソートするだけに近い感じの雰囲気の問題で、一瞬罠があるのかなと怖くなった。
問題概要
個の整数
が与えられる。
は偶数である。次の条件を満たすような整数
が何通りあるかを求めよ。
のうち、
以上の整数が
個である
のうち、
未満の整数が
個である
制約
は偶数
考えたこと
とりあえず は小さい順にソートしてしまって 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; }