• 欢迎光临~

Codeforces Round #733 D

开发技术 开发技术 2022-10-17 次浏览

D. Secret Santa

答案就是每一个数字是否出现
很容易想到的就是我们只能满足一个人的要求(如果这一组人都选择同一个人
所以我们直接就这样乱搞就可以了 然后剩下的随便连一连就行了
但是是不对的 因为剩下的几个点 我们随便连 不管按照什么方式都有可能
变成自己连自己
我们如何解决这个冲突呢
显然我们可以将该点要求满足
让被抢的那个点连接该点 这样子显然不会减少ans

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl 'n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);

void solve() {
    int n,cnt=0;cin>>n;
    vector<int>p(n+1),st(n+1),ans(n+1),v;
    map<int,int>mp;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        st[p[i]]++;
        mp[p[i]]=i;
    }
    for(int i=1;i<=n;i++)if(!st[i])v.push_back(i);
    for(int i=1;i<=n;i++){
        if(st[p[i]]==1)ans[i]=p[i],cnt++;
        else{
            ans[i]=v.back(),v.pop_back();
            st[p[i]]--;
        }
    }
    cout<<cnt<<endl;
    for (int i = 1;i <= n; i++) {
        if (i == ans[i]) {
            ans[i] = p[i];
            ans[mp[p[i]]] = i;
            mp[p[i]] = i;
        }
        cout<<ans[i]<<' ';
    }cout<<endl;
}
signed main(){
    fast
    int t;t=1;cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}
程序员灯塔
转载请注明原文链接:Codeforces Round #733 D
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com