Codeforces Round #555 (Div. 3) E. Minimum Array 【数据结构 + 贪心】
一 题面
二 分析
注意前提条件：$0 le a_{i} lt n$ 并且 $0 le b_{i} lt n$。那么，我们可以在$a_{i}$中任取一个数进行分析，发现为满足字典序最小，在$b$中找到$n-a_{i}$就是最优解。
接下来分析$b$，在$b$中是不一定找得到$n-a_{i}$的。所以需要分析如何找到此情况下的最优解。
假设$a_{i} = 3$，$n = 4$,那么$b_{i}$对应的最优情况是$b_{i} = 1$，可以把所有$b_{i}$的所有取值情况分析以下：
$b_{i} = 0$ $(a_{i}+b_{i})\%n = 3$
$b_{i} = 1$ $(a_{i}+b_{i})\%n = 0$
$b_{i} = 2$ $(a_{i}+b_{i})\%n = 1$
$b_{i} = 3$ $(a_{i}+b_{i})\%n = 2$
应该已经发现了规律了，就是以$n-a_{i}$为起点的一个循环。那么我们只要每次保证贪心取最小就可以了，这里需要运用$multiset$进行复杂度优化，但一定要注意查找的时候不能用$find$而要用$lower\_bound$，这样就可以解决了。
三 AC代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 2e5 + 15; 4 int A[MAXN], B[MAXN]; 5 6 int main() 7 { 8 //freopen("input.txt", "r", stdin); 9 int N, x; 10 multiset<int > ATree; 11 scanf("%d", &N); 12 for(int i = 0; i < N; i++) 13 scanf("%d", &A[i]); 14 for(int i = 0; i < N; i++) 15 { 16 scanf("%d", &B[i]); 17 ATree.insert(B[i]); 18 } 19 for(int i = 0; i < N; i++) 20 { 21 x = N - A[i]; 22 auto p = ATree.lower_bound(x); 23 if(p == ATree.end() ) 24 p = ATree.begin(); 25 x = *p; 26 printf("%d%c", (x + A[i]) % N , i == N -1 ? ' ':' '); 27 ATree.erase(p); 28 } 29 return 0; 30 }