CF1672F1

标签：sz int back 构造 CF1672F1 push

我们知道要是任意位置交换就是环长-1
那我们肯定要让环尽量少即可
那我们的环最多就是 出现最多的那个数字的 次数
构造策略 就是把其他不同的数字 都提出来 然后往后挪一下就可以构造出环了

void solve(){
    int n;cin>>n;
    vector<int>a(n+1),v[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v[a[i]].push_back(i);
    }
    vector<pair<int,vector<int>>>b;
    for(int i=1;i<=n;i++){
        if(v[i].size()){
            b.push_back({v[i].size(),v[i]});
        }
    }
    sort(all(b),greater<>());
    while(b[0].first) {
        vector<int>d;
        for (auto &[sz, v]: b) {
            if (sz == 0)break;
            d.push_back(v.back());
            v.pop_back();
            sz--;
        }
        for(int i=1;i<d.size();i++){
            swap(a[d[i-1]],a[d[i]]);
        }
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<' ';cout<<endl;
}

标签：sz,int,back,构造,CF1672F1,push
From： https://www.cnblogs.com/ycllz/p/17891211.html