2024国庆做题总结

Secret Santa

思路

这是一个需要深思熟虑的贪心，总之还算有点复杂。

首先，如果一个数不在它自己数值的下标上，就可以填进去，将剩下的还未填的数记录下来，此时情况如下（样例1，第一组）：

当前：2 1 _
剩余：3

然后将剩余的数的那个数组反过来，即从大到小排序，填满空位，这样可能会有冲突，但是，可以证明只会有一个冲突。

证明：\(x,y,z\) 为下标，\(a,b,c\) 分别为 \(x,y,z\) 上的数值，假设 \(y = b\)，因为 \(x < y < z\) 且 \(a > b > c\)，所以其余任何位置都无冲突。

那么如何解决掉冲突呢，将冲突位置上的值替换为之前这个位置上的值即可，再将之前这个位置上的值的现在的位置上的值改为冲突位置的值，这样就不会有冲突。

原来：2 1 3 位置 3 上有冲突
更改后：3 1 2 (第三个位置改为原来的值，第一个位置改为 3)

显然这种方案变换次数最少。

代码

#include<iostream>
#include<vector>
using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 2e5 + 10;
int T, n, ans;
int a[N], b[N], cnt[N], tot;
vector<int> v[N];
bool vis[N], f[N];

int main(){
    T = read();
    while (T--){
        n = read();
        for (int i = 1; i <= n; i++) a[i] = read(), v[a[i]].push_back(i);
        for (int i = 1; i <= n; i++){
            for (auto j : v[i]){
                if (!vis[j] && i != j){
                    b[j] = i;
                    vis[j] = 1;
                    f[i] = 1;
                    break;
                }
            }
            if (!f[i]) cnt[++tot] = i;
        }
        for (int i = 1, l = tot; i <= n && l >= 1; i++){
            if (!vis[i]) b[i] = cnt[l], l--;
        }
        for (int i = 1; i <= n; i++){
            if (b[i] == i) swap(b[i], b[v[a[i]][0]]);
        }
        for (int i = 1; i <= n; i++){
            if (a[i] == b[i]) ans++;
        }
        cout << ans << '\n';
        for (int i = 1; i <= n; i++) cout << b[i] << ' ';
        cout << '\n';
        for (int i = 1; i <= n; i++) a[i] = b[i] = cnt[i] = vis[i] = f[i] = 0;
        for (int i = 1; i <= n; i++) v[i].clear();
        tot = ans = 0;
    }
    return 0;
}