题解 CF1759G【Restore the Permutation】

problem

给定长为 \(n/2\) 的数组 \(b\)，试求出字典序最小的排列 \(p\) 使得 \(b_i=\max_{p_{2i-1},p_{2i}}\)，或者报告无解。\(n\leq 10^5\)。

solution

考虑显然的结论：\(p_{2i}=b_i\)。这时 \(p_{2i-1}<p_{2i}\) 很优。

这时相当于是剩下一些数，要去匹配这些 \(p_{2i}\)。

法一（错误）

考虑构造一组解：从小到大扫，然后匹配遇到的第一个。

然后考虑从值域出发，从小到大将一个更小的值换到前面去。可惜是 \(O(n^2)\) 的。

法二

考虑倒着扫。

因为字典序最小，也等价于大的数字尽量在后面。

维护一个堆，存放可以放的位置，每次拿最大的放。

code

typedef long long LL;
int n,a[200010],pos[200010];
int mian(){
	for(int i=1;i<=n;i++) pos[i]=0;
	for(int i=2;i<=n;i+=2) scanf("%d",&a[i]),pos[a[i]]=i-1;
	priority_queue<int> q;
	for(int i=n;i>=1;i--){
		if(pos[i]) q.push(pos[i]);
		else{
			if(q.empty()) return puts("-1"),0;
			a[q.top()]=i,q.pop();
		}
	}
	for(int i=1;i<=n;i++) printf("%d%c",a[i]," \n"[i==n]);
	return 0;
}

原文地址：http://www.cnblogs.com/caijianhong/p/solution-CF1759G.html