专栏文章

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

JJHR100330
P10276题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minx4fn7
此快照首次捕获于
2025/12/02 09:47
3 个月前
此快照最后确认于
2025/12/02 09:47
3 个月前
查看原文
构造题。
显然最后剩下 11，且 hh 最后一位一定是 11，否则无解。
其次，11 只会出现 11 或 22 次，除了 11 以外每个数在 hh 中的出现次数一定为 11，否则无解。
找到 h1h_1 至 hn−2h_{n-2} 未出现的两个数，因为要字典序最小，将小的那个放到最前面，大的那个放在最后面。
举例：
CPP
7
6 2 4 7 1 1
此时 33 和 55 未出现，将 33 放在最前，55 放在最后：
随后，依次将 h1h_1 至 hn−2h_{n-2} 放在左右的最大值旁边：
33 与 55 对比，55 更大，将 66 放在 55 左侧。
33 与 66 对比，66 更大，将 22 放在 66 左侧。
33 与 22 对比，33 更大，将 44 放在 33 右侧。
44 与 22 对比，44 更大，将 77 放在 44 右侧。
77 与 22 对比，77 更大，将 11 放在 77 右侧。
此时原数组如下：
此时按题意模拟一定能得到 hh。

代码：

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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...