[AGC059B] Arrange Your Balls

junxis · 2023-01-07 18:35:27 · 题解

Perface

Namomo Winter Camp Div.1 Day1：构造专项训练。

Analysis

令 m 为不同的颜色种类个数。

注意到答案显然有上界 m。给出构造：排序，首尾相接。

将每种颜色抽象成一个点，由于连成了一个环，那么这些点之间必然联通，那么最优的情形便是在环上相邻颜色间连边后形成一个树形结构。此时，答案便为 (m-1)。

难点在于，如何给出上述情形的构造，或判定其不存在。

如下图：

红色部分为树。我们只需延蓝色部分所画的轨迹，将沿途经过的颜色输出即可，容易发现，一个颜色被输出的次数（由绿色标出）即为其度数。

所以，每个点的度数不能超过其出现次数（无需恰好等于，多余部分在一处重复输出即可），我们只需再此条件下构造出这棵树即可。

显然，我们只需每次选度数最小的，连向较大的即可。

实质上是一层层确定叶子，只要保证叶子不连向叶子即可。

最后，dfs 模拟上图蓝色轨迹即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int, int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x; }
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for (;b;b>>=1) { if (b&1) res=res*a%mod; a=a*a%mod;} return res;}
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
// head

const int N = 201000;
int n, ext[N];
VI e[N];

void solve() {
    scanf("%d", &n);
    map<int, int> cnt;
    rep(i,1,n+1) {
        int x;
        scanf("%d", &x);
        cnt[x] += 1;
        e[i].clear();
    }
    int m = SZ(cnt);
    set<PII> st;
    for (auto [col, deg] : cnt) st.insert({deg, col});
    rep(i,1,m) {
        auto u = *st.begin(), v = *st.rbegin();
        if (u.fi <= 0 || v.fi <= 0) {
            for (auto [col, deg] : cnt) while (deg--) printf("%d ", col);
            puts("");
            return;
        } // 度数太小，无法构造出树
        st.erase(u); st.erase(v);
        e[u.se].pb(v.se); e[v.se].pb(u.se);
        ext[u.se] = u.fi - 1;  // 多余的度数
        st.insert({v.fi - 1, v.se});
    }
    auto [deg, root] = *st.begin();
    ext[root] = deg;
    VI ans;
    function<void(int, int)> dfs = [&](int u, int f) {
        ans.pb(u);
        while (ext[u]--) ans.pb(u);
        for (auto v : e[u]) if (v != f) {
            dfs(v, u);
            ans.pb(u);
        }
    };
    dfs(root, 0);
    ans.pop_back(); // 最后回到起点多加了一次
    for (auto c : ans) printf("%d ", c); puts("");
}

int main() {
    int _;
    for (scanf("%d", &_); _; _--) {
        solve();
    }
}