2020 年百度之星·程序设计大赛 - 复赛 rk:69 pros:3/6

Codeforces Round #664 (Div. 1) rk:131 pros:2/5

atcoder abc 174

cf round 661

cf 1382e mastermind

tag：贪心

题意：给n,x,y和一个长n的数组，数组元素的大小为1到n+1间的整数，求另一个数组，元素大小同样在1到n+1，两个数组元素相同的位置有x个，重新排列后两个数组最多有y个相同位置的元素相同

题解：首先对出现的元素进行计数，显然要把x的指标优先给数量多的元素

这样还剩下n-x个元素，对于这n-x个元素，两个数组在不重新排列前不能有匹配，对于一某种元素c，假设它有k个，如果2*k>n-x，那么必然有一部分元素要变成其它的元素，n个位置有n+1种元素，所以这个用来替换的元素是一定存在的，而如果出现这样的情况，n-x这一部分在重排之后至多能匹配2*(n-x-k)个，也就是要2*(n-x-k)>=y-x，化简得2*n-x-y>=2*k，不满足则无解

对于有解的情况就比较简单了，对n-x这部分的元素排序，然后旋转(n-x)/2之后放进去，再把n-y个位置的元素换成不存在过的元素就可以了

comment：很妙的题，尤其是对于无解的判断