题解：P10276 [USACO24OPEN] Farmer John's Favorite Permutation B
JHR100330
·
·
题解
构造题。
显然最后剩下 1，且 h 最后一位一定是 1，否则无解。
其次，1 只会出现 1 或 2 次，除了 1 以外每个数在 h 中的出现次数一定为 1，否则无解。
找到 h_1 至 h_{n-2} 未出现的两个数，因为要字典序最小，将小的那个放到最前面，大的那个放在最后面。
举例：
7
6 2 4 7 1 1
此时 3 和 5 未出现，将 3 放在最前，5 放在最后：
随后，依次将 h_1 至 h_{n-2} 放在左右的最大值旁边：
$3$ 与 $6$ 对比，$6$ 更大，将 $2$ 放在 $6$ 左侧。
$3$ 与 $2$ 对比，$3$ 更大，将 $4$ 放在 $3$ 右侧。
$4$ 与 $2$ 对比，$4$ 更大，将 $7$ 放在 $4$ 右侧。
$7$ 与 $2$ 对比，$7$ 更大，将 $1$ 放在 $7$ 右侧。
此时原数组如下：
此时按题意模拟一定能得到 $h$。
## 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls(x) x << 1
#define rs(x) x << 1 | 1
const int N = 100050;
int t, n, h[N], cnt[N], lnow, rnow;
vector<int> l, r;
int main() {
cin >> t;
while(t --){
cin >> n;
for(int i = 1; i <= n; i ++)
cnt[i] = 0;
for(int i = 1; i < n; i ++){
cin >> h[i];
cnt[h[i]] ++;
}
if(cnt[1] > 2 || cnt[1] == 0){puts("-1"); continue;}
if(h[n - 1] != 1){puts("-1"); continue;}
int f = 0;
for(int i = 2; i <= n; i ++)
if(cnt[i] > 1){puts("-1"); f = 1; break;}
if(f) continue;
cnt[1] --;
for(int i = 1; i <= n; i ++)
if(cnt[i] == 0) rnow = lnow, lnow = i;
if(lnow > rnow) swap(lnow, rnow);
l.clear(), r.clear();
l.push_back(lnow); r.push_back(rnow);
for(int i = 1; i < n - 1; i ++){
if(lnow > rnow){
l.push_back(h[i]);
lnow = h[i];
}
else{
r.push_back(h[i]);
rnow = h[i];
}
}
for(int i : l) cout << i << " ";
reverse(r.begin(), r.end());
for(int i : r) cout << i << " ";
cout << endl;
}
return 0;
}
```