典型90問
007 - CP Classes（★3）
- 問題を見て二分探索がすぐに思いついた。とても良かった。
- 0indexにする方が楽だったのだが最初1indexにしてしまったために少しミスってしまった。
- 二分探索は基本的に0indexがよさそう
- ソートするのを忘れない
int main() {
long long N;
cin >> N;
vector<long long> A(N);
for (long long i = 0; i < N;i++){
cin >> A[i];
}
sort(A.begin(),A.end());
long long Q;
cin >> Q;
for (long long i = 0; i < Q;i++){
long long B;
cin >> B;
auto it = lower_bound(A.begin(),A.end(),B);
if (it == A.end()){
cout << abs(A[N - 1] - B) << endl;
}else if (it == A.begin()){
cout << abs(A[0] - B) << endl;
}else{
long long idx = it - A.begin();
cout << min(abs(A[idx] - B),abs(A[idx - 1] - B)) << endl;
}
}
}
014 - We Used to Sing a Song Together（★3）
- 流石に難しい
- 直感的に「ソート、二分探索、配列の取り出し」の組み合わせをセットにしてできるかなと思ったが選択する学校の重複や空きは許されないため生徒側の取り出し方とそのマッチングに対して本当にそれが最適化を証明できないと思った。そもそも計算量も怪しい
- 両方ともソートして先頭から足していけばいける？と思ったが直感的に怪しい気がして（★3,3Q問題という先入観）試さず
→これが答えだったっぽい。
int main() {
long long N;
cin >> N;
vector<long long> A(N);
vector<long long> B(N);
for (long long i = 0; i < N;i++){
cin >> A[i];
}
for (long long i = 0; i < N;i++){
cin >> B[i];
}
sort(A.begin(),A.end());
sort(B.begin(),B.end());
long long ans = 0;
for (long long i = 0; i < N;i++){
ans += abs(A[i] - B[i]);
}
cout << ans << endl;
}