[Codeforces Round #658 (Div. 1)] C. Mastermind（构造）
In the game of Mastermind, there are two players — Alice and Bob. Alice has a secret code, which Bob tries to guess. Here, a code is defined as a sequence of nn colors. There are exactly n+1n+1 colors in the entire universe, numbered from 11 to n+1n+1 inclusive.
When Bob guesses a code, Alice tells him some information about how good of a guess it is, in the form of two integers xx and yy.
The first integer xx is the number of indices where Bob's guess correctly matches Alice's code. The second integer yy is the size of the intersection of the two codes as multisets. That is, if Bob were to change the order of the colors in his guess, yy is the maximum number of indices he could get correct.
For example, suppose n=5n=5, Alice's code is [3,1,6,1,2][3,1,6,1,2], and Bob's guess is [3,1,1,2,5][3,1,1,2,5]. At indices 11 and 22 colors are equal, while in the other indices they are not equal. So x=2x=2. And the two codes have the four colors 1,1,2,31,1,2,3 in common, so y=4y=4.
Solid lines denote a matched color for the same index. Dashed lines denote a matched color at a different index. xx is the number of solid lines, and yy is the total number of lines.
You are given Bob's guess and two values xx and yy. Can you find one possibility of Alice's code so that the values of xx and yy are correct?
Input
The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases. Next 2t2t lines contain descriptions of test cases.
The first line of each test case contains three integers n,x,yn,x,y (1≤n≤105,0≤x≤y≤n1≤n≤105,0≤x≤y≤n) — the length of the codes, and two values Alice responds with.
The second line of each test case contains nn integers b1,…,bnb1,…,bn (1≤bi≤n+11≤bi≤n+1) — Bob's guess, where bibi is the ii-th color of the guess.
It is guaranteed that the sum of nn across all test cases does not exceed 105105.
题意：
给定一个长度为(mathit n)的数组(mathit a)和两个整数(x,y,xleq yleq n)。
让你构造一个数组(mathit b)，长度为(mathit n)，且(b_iin [1,n+1])，且有(mathit x)个(i,a_i=b_i)，且有(mathit y)个在(mathit b)数组中出现的数字在(mathit a) 中出现。
思路：
先用优先队列或者计数桶完成以下操作(mathit x)次：
每次选一个当前数组(mathit a)中出现次数最大（并且的话选择任意一个即可）的数(a_i)让其(b_i=a_i)，然后将(a_i)从桶中删除。
再次操作之后，(mathit b)中还剩下(n-x)个位置没有填数字。
设(num)为执行上边操作后剩余数字中出现频率次数最高的那个数字的频率。
我们可以发现，无论怎么重新构造数组(a_i)剩余数字的顺序，最优的与原数组(a_i)相等位置数字相同的个数为(forced=max(0,num*2-(n-x)))。
我们知道我们可以找到一个数字(mathit e otin a)，（因为(ein[1,n+1],|a|=n)）。
当答案数组的(forced>0)，肯定是不符合条件的，因为(b_i=a_i)的数量大于(mathit x)。
我们可以用(mathit e)去替换一些被迫与数组(a_i)相等的(b_i)，从而降低(forced)。
那么如果(n-y<forced)，即无论怎么安放和替换，最后的答案数组(mathit b) 一定是(b_i=a_i)的数量大于(mathit x)，可以直接输出(NO)。
否则就一定可以构造出合法的方案，
最优的处理数组(a_i)剩余数字方法为：
用数组(mathit v)存储数组(a_i)剩余数字的下标，其中相同颜色的下标要相邻放。
易得数组(mathit v)的大小为(len=n-x)。
那么将数组(v)的每一个数值向右滚动(len/2)个位置（超出(len)的移动到左侧，想象成一个圆更好理解。）
这样得到的(forced=max(0,num*2-(n-x)))，那么将(b_i=a_i)的(b_i=e)即可，然后根据(mathit y)的数字将一些(b_i)替换为(mathit e)即可。
时间复杂度分析：
用堆之类的处理的话为：(O(sum n_i*log(n_i)))
用桶的处理的话为：(O(sum n_i))
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), ' ', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("
");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("
");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '
' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '
' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
int n, x, y;
std::vector<int> index[maxn];
std::vector<int> ran[maxn];
int a[maxn];
int ans[maxn];
bool solved[maxn];
void modify_to_unvised(int id, int & need)
{
ans[id] = ran[0][0];
need--;
solved[id] = 1;
}
int main()
{
#if DEBUG_Switch
freopen("C:\code\input.txt", "r", stdin);
#endif
//freopen("C:\code\output.txt","w",stdout);
int t;
t = readint();
while (t--)
{
n = readint();
x = readint();
y = readint();
repd(i, 1, n)
{
int x = readint();
index[x].push_back(i);
a[i] = x;
}
repd(i, 1, n + 1)
{
ran[sz(index[i])].push_back(i);
}
int id = n;
repd(i, 1, x)
{
while (ran[id].size() == 0)
id--;
int col = ran[id].back();
ran[id].pop_back();
int pos = index[col].back();
ans[pos] = col;
ran[id - 1].push_back(col);
index[col].pop_back();
}
while (ran[id].size() == 0 && id > 0)
id--;
if (2 * id - (n - x) > n - y)
{
printf("NO
");
} else
{
std::vector<int> v;
for (int i = id; i >= 1; --i)
{
for (auto w : ran[i])
v.insert(v.end(), ALL(index[w]));
}
int need = n - y;
int len = n - x;
for (int i = 0; i < len; ++i)
{
ans[v[i]] = a[v[(i + len / 2) % len]];
if (ans[v[i]] == a[v[i]])
{
modify_to_unvised(v[i], need);
}
}
int i = 0;
while (need > 0)
{
if (!solved[v[i]])
{
modify_to_unvised(v[i], need);
}
i++;
}
printf("YES
");
repd(i, 1, n)
{
printf("%d%c", ans[i], i == n ? '
' : ' ' );
}
}
repd(i, 0, n + 1)
{
index[i].clear();
ran[i].clear();
solved[i] = 0;
}
}
return 0;
}