P3566

K7mQ2xR9pL4v · 2023-11-15 18:54:16 · 题解

考虑贪心。

由于本题中开头结尾 p,q 被固定，仅需填从 2 \sim n-1 中的数。

然后就有一个简单的贪心策略，使用数据结构维护当前最大数量，每次填数，看数量最大的那个东西是否与前面填的一致，如果不一致的话直接填，一致就只能换次大的去填了。

但是发现光这么贪存在某些谬误，例如可能会输出末尾两个数一样的，例如输出 1 2 1 3 1 2 3 1 2 3 3，显然这种情况下是存在正解为 1 3 2 1 3 2 1 3 2 1 3 等的，于是贪心条件需要再加一条：考虑同等数量的不同的数，优先使用 q 进行填充，这样可以保证如果存在有解 q 一定不是最后一个被填的。

然后做完了，spj 不知道写的什么烂东西。

int n, x, y;
struct node {
    int first, second;
    bool operator < (const node &a) const {
        if (a.first == first) return second != y;
        return first < a.first;
    }
};
priority_queue<node> q;
int ans[1010101];
signed main() {
    n = read(), x = read(), y = read();
    for (int i = 1; i <= n; ++i) {
        int a = read();
        if (i == x) --a;
        if (i == y) --a;
        if (a < 0) return printf("0"), 0;
        q.push({a, i});
    }
    ans[1] = x;
    int len = 1;
    int last = x;
    while (!q.empty()) {
        auto tp = q.top();
        q.pop();
        if (q.size() && tp.second == last) {
            auto tp2 = q.top();
            q.pop();
            ans[++len] = tp2.second;
            tp2.first--;
            last = tp2.second;
            if (tp2.first) q.push(tp2);
            q.push(tp);
        } else if (q.size() && tp.second != y && tp.first == q.top().first && q.top().second != last && q.top().second == y) {
            auto tp2 = q.top();
            q.pop();
            last = tp2.second;
            ans[++len] = tp2.second;
            tp2.first--;
            if (tp2.first) q.push(tp2);
            q.push(tp);
        } else if (tp.second == last) {
            return printf("0"), 0;
        } else {
            tp.first--;
            ans[++len] = tp.second;
            if (tp.first) q.push(tp);
            last = tp.second;
        }
    }
    if (last == y) return printf("0"), 0;
    ans[++len] = y;
    for (int i = 1; i <= len; ++i) {
        if (i != len) write(ans[i], ' ');
        else printf("%lld", ans[i]);
    }
    return 0;
}