题解 P9467 [EGOI2023] Carnival General

GI录像机 · 2023-10-30 14:14:35 · 题解

思路：

我们考虑从 0 到 N-1 依次把每个总管加入序列，把新总管任意插到序列中的一个合法位置内。

一个总管能够加入序列当且仅当序列中存在一个“空”，使得和这个“空”相邻的总管排名都在前一半。

我们用 0 表示对于 i 排名在前一半的总管，1 表示排名在后一半的总管。

若当前序列中已经有 len 个数。

当 len 为偶数时，最坏情况下序列会变成 1 0 1 0\cdots 0，必有至少一个位置可以插入。（因为如果有两个相邻的 1 就可以直接插到中间）

当 len 为奇数时，最坏情况下序列会变成 1 0 1 0\cdots 1，必有至少一个位置可以插入。

综上，这种方法必然能构造出一种解。

代码：

#include<bits/stdc++.h>
using namespace std;
int read() {
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return f * x;
}
void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 2e5 + 10, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
int n = read();
bool ok[N];
vector<int>ans;
signed main() {
    ans.push_back(0);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int tmp = read();
            if (j < i - i / 2)ok[tmp] = 1;
            else ok[tmp] = 0;
        }
        if (ok[ans[i - 1]])ans.push_back(i);
        else {
            for (int j = 0; j < i; j++) {
                bool flag = ok[ans[j]];
                if (j)flag = flag && ok[ans[j - 1]];
                if (flag) {
                    ans.insert(ans.begin() + j, i);
                    break;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        write(ans[i]);
        putchar(' ');
    }
    return 0;
}