2023年3月20日 https://codeforces.com/problemset/problem/1157/E
输入 n(≤2e5) 和两个长为 n 的数组 a b,元素范围在 [0,n-1]。
你可以重排数组 b。
还有一个长为 n 的数组 c,其中 c[i] = (a[i] + b[i]) % n。
输出字典序最小的 c。
a[i] + b[i] <= 2 * n - 2 <= 2 * n;
如果存在 (a[i] + b[i]) > n 即选择b[i] > n - a[i]最小的为局部最优解
如果存在 (a[i] + b[i]) <= n 那么选择b[i]最小的为局部最优解
两个局部最优取全局最优
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int a[N], b[N], c[N];
int main (){
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
for(int i = 0; i < n; i ++) cin >> b[i];
multiset<int> S;
for(int i = 0; i < n; i ++) S.insert(b[i]);
for(int i = 0; i < n; i ++){
int ans = n - a[i];
auto pos = S.find(ans);
if(pos != S.end()){
c[i] = 0;
S.erase(pos);
continue;
}
int x = *S.begin();
int y = n - a[i];
auto p = S.lower_bound(y);
if(p == S.end()){
c[i] = (x + a[i]) % n;
S.erase(S.begin());
}
else{
int ans1 = (x + a[i]) % n, ans2 = (*p + a[i]) % n;
if(ans1 <= ans2){
c[i] = (x + a[i]) % n;
S.erase(S.begin());
}
else{
c[i] = (*p + a[i]) % n;
S.erase(p);
}
}
}
for(int i = 0; i < n; i ++) cout << c[i] << ' ';
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int a[N], b[N], c[N];
int main (){
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
for(int i = 0; i < n; i ++) cin >> b[i];
multiset<int> S;
for(int i = 0; i < n; i ++) S.insert(b[i]);
for(int i = 0; i < n; i ++){
int target = n - a[i];
auto pos = S.lower_bound(target);
if(pos == S.end()){
pos = S.begin();
}
c[i] = (a[i] + *pos) % n;
S.erase(pos);
}
for(int i = 0; i < n; i ++) cout << c[i] << ' ';
return 0;
}