【競プロ】1日1AC : ABC94 C問題

今日もちゃんと更新します。今日の問題はこちら。

Diffは558（茶）です。
是非解いてから読み進めてください。

提出コードと考え方

\(X\) をソートした配列 \(Y\) を用意します。実験してみるとわかるのですが、中央値になりうるのは \(Y_{N/2},Y_{N/2-1}\) だけです。\(X\) から除く値が \(Y_{N/2}\) より前であるとき、出力するべき値は \(Y_{N/2}\) になり、それ以外の時は \(Y_{N/2-1}\) になります。

見やすくなるように式で書いておきます。\(X\) から除く値を \(R_i\) とすると
\[
B_i=\begin{cases}
Y_{N/2}&(R_i<Y_{N/2})\\
Y_{N/2-1}&(otherwise)
\end{cases}
\]
です。

以下が提出コードです。

#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;

int main(){
    int n;
    cin >> n;
    vector x(n);
    rep(i,n) cin >> x[i];
    vector y(x);
    sort(y.begin(),y.end());
    rep(i,n){
        if(x[i] < y[n/2]) cout << y[n/2] << endl;
        else cout << y[n/2 - 1] << endl;
    }
    return 0;
}

ちなみに、vectorの宣言の時に

vector y(x);

のようにすると宣言と同時に要素のコピーができます。