2021牛客暑期多校训练营10_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

F-Train Wreck

本题题意有些复杂，转换下题意就是给你一棵树，以及不同的颜色数，现在让你对这棵树进行染色，要求每个节点的儿子节点颜色互不相同。

很容易看出来，我们可以贪心地达到目的，每次先使用最多的颜色去染色即可，那么本题的重点就是如何建出这棵树，具体如下：

依次遍历给定的括号序列并维护一个栈，保证下一个遍历到的左括号的父亲是栈顶：

\(\bullet\) 如果是左括号\((\)，我们按顺序给他们编号，并让它入栈。

\(\bullet\) 如果是右括号\()\)，我们弹出栈顶。

这样做之后会发现有一个问题，如果是\(()()()\)这样的序列那么我们接下来的程序会认为\(1~1~1\)也是合法的，所以我们可以在最开始先在栈中添加一个虚拟节点\(0\)。

那么样例二根据括号序列建出来的树就是这样的 \(\downarrow \downarrow \downarrow\)

接下来只要贪心地染色就行了，具体地，我们可以用一个优先队列存储每个颜色的个数和编号并且让个数多的优先出队，然后依次枚举每个节点即\(0 \cdots n\)，再枚举它的所有儿子节点，并且依次让队列元素出队并记录颜色，那么不能染色的条件就是当前队列颜色个数\(<\)当前节点儿子个数。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 5;
struct Color {
    int col, cnt;
    bool operator <(const Color &oth) const {
        return cnt < oth.cnt;
    }
};
char s[MAXN];
int n, M[MAXN];
vector<int> e[MAXN];
void build() {
    stack<int> S;
    S.push(0); // 虚拟节点, 永远在栈中
    int idx = 0; // 每个左括号(的编号
    for (int i = 1; i <= 2 * n; ++i) {
        if (s[i] == '(') {
            e[S.top()].push_back(++idx);
            S.push(idx);
        }
        else {
            S.pop();
        }
    }
}
int ans[MAXN];
void solve() {
    priority_queue<Color> Q;
    for (int i = 1; i <= n; ++i) {
        if (M[i]) {
            Q.push({i, M[i]});
        }
    }
    for (int u = 0; u <= n; ++u) {
        // 如果 队列里的颜色 < 儿子个数
        if (Q.size() < e[u].size()) {
            cout << "NO" << '\n';
            return ;
        }
        // 因为要保证儿子节点颜色各不相同 
        // 所以我们在出队后先保存下来 
        // 等全部染色后再入队 
        // 这样就保证了颜色不同
        vector<Color> V;
        for (int v: e[u]) {
            auto [col, cnt] = Q.top(); Q.pop();
            ans[v] = col;
            // 如果当前颜色-1之后为0就不用再次入队了
            if (cnt > 1) {
                V.push_back({col, cnt - 1});
            }
        }
        // 用过的颜色重新入队
        for (auto [x, y]: V) {
            Q.push({x, y});
        }
    }
    cout << "YES" << '\n';
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " \n"[i == n];
    }
}
int main(int argc, char *argv[]) {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> s + 1;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        ++M[x]; // 记录这个颜色个数
    }
    build(); // 根据括号序列建树
    solve(); // 贪心
    system("pause");
    return 0;
}