C
l が奇数のとき,l 個の数 a1,a2,…,al の中央値とは,a1,a2,…,al の中で
l+1
2
番目に大きい値のことを言います.
N 個の数 X1,X2,…,XN が与えられます.ここで,N は偶数です. i=1,2,…,N に対して,X1,X2,…,XN から Xi のみを除いたもの,すなわち X1,X2,…,Xi−1,Xi+1,…,XN の中央値を Bi とします.
i=1,2,…,N に対して,Bi を求めてください.
制約
2≤N≤200000
N は偶数
1≤Xi≤109
入力はすべて整数
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
using ll = long long;
int main() {
int N;
cin >> N;
vector<int>V(N);
for (int i = 0; i < N; ++i) {
cin >> V[i];
}
for (int i = 0; i < N; ++i) {
vector<int>v = V;
v.erase(v.begin() + i);
sort(v.begin(), v.end());
cout << v[(N - 2) / 2] << endl;
}
return 0;
}
tle
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
using ll = long long;
int main() {
int N;
cin >> N;
vector<int>V(N);
vector<int>Y(N);
for (int i = 0; i < N; ++i) {
cin >> V[i];
Y[i] = V[i];
}
sort(V.begin(), V.end());
for (int i = 0; i < N; ++i) {
if (Y[i] < V[N / 2 - 1])
cout << V[N / 2] << endl;
else if (Y[i] > V[N / 2])
cout << V[N / 2 - 1] << endl;
else if (Y[i] == V[N / 2 - 1])
cout << V[N / 2] << endl;
else if (Y[i] == V[N / 2])
cout << V[N / 2 - 1] << endl;
}
return 0;
}
ちょっとだけ早く