Favorite Permutation (USACO Bronze 2024 US Open)

Favorite Permutation (USACO Bronze 2024 US Open)

1-N的数字组成的排列，每次删除头尾中较大的数，并写下第二个（删除头时），或者倒数第二个数（删除尾时）。要求通过写下的数，来恢复原来的排列。

我们可以做一些系列观察：

  1. 一个写下来的数字，要不就是左边的数被删了，要不就是右边的数字被删了，而一个方向的邻居最多只能被删除一次，所以一个数字最多出现两次。
  2. 因为每次都删大的，永远删不到1，因此最后一个写下来的数字一定是1。
  3. 可以看到，其实是固定住1的位置之后，一会删左边，一会删右边，直到最后写下1结束。这样我们就会发现上面第一个规律还不够准确， 实际情况就是只有1会出现两次，其它数字最多出现一次。
  4. 没有出现过的数字，如果有两个，那么就是最边上的数字。对应的，此时1会出现两次。
  5. 如果1只出现了一次，那么1一定在边上，另外一边就是没有出现的数字。

到这里，我们就可以得到一个恢复原有排列的算法了：

  1. 通过没有出现的数字，确定原排列中最左最右的数字：如果两个没出现，那就一左一右，如果一个数字没出现，那就是这个数字和1是左右两侧的数字。
  2. 因为结果需要输出字典序最小的结果，所以我们把小的数字放左边。
  3. 然后我们会删除左右两边数字中较大的（第一步一定是右边），这时就可以把写下来的数字填入对应位置。
  4. 重复这个过程，就可以一步步恢复出整个数字序列了。
#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int T, n;
int a[100005], b[100005];
bool f[100005];
 
int main() {
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        int ones = 0;
        bool valid = true;
        memset(f, 0, sizeof(f));
        scanf("%d", &n);
        for (int i = 0; i < n-1; i++) {
            scanf("%d", &a[i]);
            if (a[i] != 1 && f[a[i]])       // non-1 num can appear at most once
                valid = false;
            f[a[i]] = true;
            if (a[i] == 1)
                ones++;
        }
        if (a[n-2] != 1) valid = false;     // the last num is always 1
        if (ones > 2) valid = false;        // 1 can appear at most twice
        if (!valid) {
            printf("-1\n");
            continue;
        }
        vector<int> missing;
        for (int i = 1; i <= n; i++)
            if (!f[i])
                missing.push_back(i);
        int l = 0, r = n-1;
        if (ones == 1) {                    // fill in outer-most nums
            b[0] = 1;
            b[n-1] = missing[0];
        } else {
            b[0] = min(missing[0], missing[1]);
            b[n-1] = max(missing[0], missing[1]);
        }
        for (int i = 0; i < n-1; i++) {     // fill in remaining nums one by one
            if (b[l] > b[r]) {
                b[l+1] = a[i];
                l++;
            } else {
                b[r-1] = a[i];
                r--;
            }
        }
        for (int i = 0; i < n; i++)
            printf("%d ", b[i]);
        printf("\n");
    }
 
    return 0;
}