Poj2182 Lost Cows（玄学算法）

发表于 | 更新于 | 分类于
本文字数： 908 | 阅读时长 ≈ 2 分钟

题面

Poj

题解

不难发现最后一位就是$pre[n]+1$，然后消除这个位置对其他位置的贡献，从左到右扫一遍，必定有至少一个位置可以得出，循环这个过程，$O(n^2)$出解。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
typedef long long ll;

const int N = 8e4 + 10;
int n, pre[N], a[N], less[N];
bool used[N];

template<typename T>
void read(T &x) {
    x = 0; char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}

int main () {
    read(n);
    for(int i = 2; i <= n; ++i) read(pre[i]), less[i] = i - 1;
    a[n] = pre[n] + 1, used[a[n]] = true;
    for(int i = a[n] + 1; i <= n; ++i) --less[i];
    for(int i = n - 1; i >= 1; --i) {
        for(int j = 1; j <= n; ++j)
            if(less[j] == pre[i] && !used[j]) { a[i] = j, used[a[i]] = true; break; };
        for(int j = a[i] + 1; j <= n; ++j) --less[j];
    }
    for(int i = 1; i <= n; ++i)
        printf("%d\n", a[i]);
    return 0;
}