题意：
n个人，每个人选择自己喜欢的人送礼物，但是不能选自己，题目给出最初的每个人喜欢送的人，问构造一个序列，要使尽可能多的人能够送给自己喜欢送的人，而且自己不能送给自己
思路：
- 要满足送给自己喜欢的人的人数最多，那对于出现一次的，直接选即可，如果出现多个人喜欢送一个人，那最多的贡献就是1，所以这个贡献是很容易求
- 已经分配好了单一人喜欢送一个人的情况，先把那些无人喜欢的人存下来，剩下的对于一个人，多个人喜欢送他，那先把满足一个人，那就相当于满足最大的贡献了，然后剩下的人从无人喜欢的人里分配，分配好了，还要判断是否可能自己送自己，对于自己送自己，其实有一个很好的方法，就是在当前的区间里，不断的和相邻的互换，如果是尾端，就和首端进行互换
总结：
两段序列，要是每个数都不是两两相等排列，问要怎么构造，先随机乱排，然后判断是否相等，如果相等的话，直接互换
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
int T, n;
set<int> st[MAXN];
bool comp(pair<int, int> x, pair<int, int> y)
{
return x.first < y.first;
}
void init()
{
for (int i = 1; i <= n; ++i)
st[i].clear();
}
int main()
{
IOS; cin.tie(0), cout.tie(0);
cin >> T;
while (T--)
{
cin >> n;
init();
map<int, int> mp, mpe;
for (int i = 1, x; i <= n; ++i)
{
cin >> x;
st[x].insert(i), mp[x]++, mpe[i] = x;
}
deque<int> q;
for (int i = 1; i <= n; ++i)
if (mp[i] == 0)
q.push_back(i);
int k = 0;
vector<pair<int, int>> ans;
for (int i = 1; i <= n; ++i)
{
if (st[i].size() == 1)
ans.push_back({*(st[i].begin()), i}), ++k;
else
{
int pos = ans.size() - 1;
for (auto it = st[i].begin(); it != st[i].end(); ++it)
{
if (it == st[i].begin())
ans.push_back({*it, i}), ++k;
else
{
if (q.back() != *it)
ans.push_back({*it, q.back()}), q.pop_back();
else
ans.push_back({*it, q.front()}), q.pop_front();
}
}
for (int j = pos + 1; j < ans.size(); ++j)
{
if (ans[j].first == ans[j].second)
{
if (j + 1 < ans.size())
{
ans[j].second = ans[j + 1].second;
ans[j + 1].second = ans[j].first;
}
else
{
ans[j].second = ans[pos + 1].second;
ans[pos + 1].second = ans[j].first;
}
}
}
}
}
sort(ans.begin(), ans.begin() + n, comp);
cout << k << endl;
for (int i = 0; i < n; ++i)
cout << ans[i].second << " ";
cout << endl;
}
return 0;
}
/*
1
3
2 1 2
*/