B Arrange Your Balls (agc059)

B - Arrange Your Balls (agc059)

tag：构造 思维 欧拉序

题目链接

题意：

给出一堆小球，小球带有颜色，让你把小球排成一个环，若相邻两个小球颜色不同，则功德加1，问你如何按排使得贡献最少

做法：

设小球颜色种类数为m
我们可以想到一种很简单总贡献为m的构造，即把相同颜色的都拍一起 比如：1 1 2 2 3 3 3

那么有没有贡献更少的构造呢？
在此之前我们先来看一下欧拉序
所谓欧拉序，就是从根节点出发，按dfs的顺序访问后再绕回原点的顺序，具体见下图

现在让我们发挥想象力把这些蓝色的边撑开

我们得到的欧拉序即为 1-3-4-3-2-3-5-3-6-3
若样例为 1 2 3 3 3 3 3 4 5 的时候，上图即为一个合法构造
当然这只是恰好的情况，假如颜色为5的球有多，我们只需要在上述欧拉序中最后一次出现5的地方把剩下的插完就ok

讲完构造的方法，让我们来思考两个问题
一、存在贡献更少的方案吗？
把颜色抽象为点，一种颜色至少会和另一种颜色相邻，一条边就是一次贡献，图得保证联通，那么最优情况只能是树
二、什么情况下才能使用第二种构造？
在得到欧拉序的过程中,我们遍历了一棵树两次，所以n至少得大于2*(m-1)

代码：

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
const int mod=998244353;
vector<int> g[N];
struct node{
    int id,d; //编号 度数
    bool operator<(const node &x) const{
        return d<x.d;
    }
};

void solve(){
    int n; cin>>n;
    vector<int> a(n+1),cnt(n+1);

    int m = 0; //统计种类数
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!cnt[a[i]]) m++;
        cnt[a[i]]++;
        g[i].clear();
    }

    if(n<2*m-2||m==1){
        sort(a.begin(),a.end());
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" \n"[i==n];
        }
        return;
    }
    //建树方法很多，我这边用的双端队列
    //我们只要注意一种情况，除非是连最后一条边，不要把两个度数为一的点连起来就行，否则就不是树了
    deque<node> q;
    for(int i=1;i<=n;i++){
        if(cnt[i]){
            q.push_back({i,cnt[i]});
        }
    }
    sort(q.begin(),q.end());
    //让队头度数小的连队尾度数大的，若队尾剩余度数为1，就让队尾到队头来
    int tmp = q.back().d;
    while(q.size()!=2){
        if(tmp==1) {
            node tt = q.back();
            tt.d = 1;
            q.pop_back();
            tmp = q.back().d;
            q.push_front(tt);
        }
        g[q.back().id].push_back(q.front().id);
        g[q.front().id].push_back(q.back().id);
        q.pop_front();
        tmp--;
    }
    g[q.back().id].push_back(q.front().id);
    g[q.front().id].push_back(q.back().id);
   
    
    function<void(int,int)> dfs = [&](int u,int fa){
        int count = 0;
        if(u!=q[0].id) cout<<u<<" ",count++;//记得对第一个点特判
        for(auto v: g[u]){
            if(v==fa) continue;
            dfs(v,u);
            count++;
            cout<<u<<" ";
        }
        for(int i=count+1;i<=cnt[u];i++) cout<<u<<" ";
    };

    dfs(q[0].id,-1);
    cout<<le;
}

int main() {
    fst; 
    int t; cin>>t;
    while(t--){
        solve();
    }   
    return 0;
}