题解：P10276 [USACO24OPEN] Farmer John's Favorite Permutation B

· · 题解

已知

首先，只要读题 再用脑子加以推断可知以下几点。

一切起源于1是最小的。

分类讨论

  1. 有两时：肯定有两没输入的。 放置首与尾（因字典序要小，小前大后）。

  2. 有一时：1 肯定在首，没输入的放尾。

然后统一比较首尾大小，大 h 放后，小 h 放前。

特殊情况

答案为 -1 时: 一的数量 > 二 or 其他数量 \ge 二 or h 的末尾不是一。

综上 代码

#include <bits/stdc++.h>
using namespace std;
int h[500005], t, n, a[500005], ans[500005];//a为桶，ans为答案 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    for (int i = 1; i <= t; i++) {
        memset(ans, 0, sizeof(ans));
        memset(a, 0, sizeof(a));           //谨记清空 
        cin >> n;
        int l = 1, r = n;
        for (int j = 1; j < n; j++)cin >> h[j], a[h[j]]++;//输入计入桶 

        if (h[n - 1] != 1 || a[1] > 2) {//特殊情况 
            cout << "-1" << "\n";
            continue;
        }
        if (n == 2) {
            cout << "1 2" << "\n";//本人太懒 
            continue;
        }
        bool ye = 1;
        for (int j = 2; j <= n; j++)
            if (a[j] >= 2) {
                cout << -1 << "\n";//特殊情况 
                ye = 0;
                break;
            }
        if (ye == 0)continue;
        if (a[1] == 2) {                //1有两个时 
            int x = 0, y = 0;
            for (int j = 2; j <= n; j++) {//两没有的 
                if (a[j] == 0) {
                    if (!x)x = j;
                    else {
                        y = j;
                    }
                }
                if (a[j] >= 2) {
                    cout << -1 << "\n";
                    continue;
                }
            }

            if (x > y)swap(x, y);
            ans[1] = x;
            ans[n] = y;
            for (int j = 1; j < n; j++) {//比大小 
                if (ans[l] < ans[r]) {
                    ans[--r] = h[j];
                } else {
                    ans[++l] = h[j];
                }
            }
            for (int j = 1; j <= n; j++)cout << ans[j] << " ";//答案 
            cout << "\n";
        } else {//第二种情况 
            ans[1] = 1;
            for (int j = 2; j <= n; j++) {
                if (a[j] == 0) {//没有的 
                    ans[n] = j;
                }
                if (a[j] >= 2) {
                    cout << -1 << "\n";
                    continue;
                }
            }
            for (int j = 1; j < n; j++)ans[--r] = h[j];//放入 
            for (int j = 1; j <= n; j++)cout << ans[j] << " ";//答案 
            cout << "\n";
        }
    }
    return 0;
}