P3034 [USACO11DEC] Cow Photography G/S 题解

P3034 [USACO11DEC] Cow Photography G/S 题解

模拟赛考到的题，来发题解。

解法

因为题中说如果一头奶牛在拍其中一张照片时移动了，它在拍其他四张照片的时候都不会移动，所以设有两头奶牛 $A$ 和 $B$，其中 $A$ 应该在 $B$ 的前面，那只有当奶牛 $A$ 跑到 $B$ 后面或者 奶牛 $B$ 跑到 $A$ 前面这两种情况能让两头奶牛的相对位置互换，所以对于这 $5$ 张照片，如果一头奶牛在另一头奶牛之前的位置超过 $5-2=3$ 次，则表明这头奶牛应该在那头奶牛的前面，他们的相对位置就确定下来了。我们只需要确定所有奶牛的相对位置即可。知道了所有奶牛的相对位置即可知道所有奶牛的绝对位置。这个可以在排序的过程中实现。

时间复杂度 $\mathcal{O}(n\log n)$，瓶颈在于排序。

代码

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
	/*
	fast Input/Output
	*/
};
using namespace fast_IO;
int n;
struct cow
{
	int x,pos[6];
	inline bool operator<(const cow &rhs) const
	{
		int cnt=0;
		for(int i=1;i<=5;i++) if(pos[i]<rhs.pos[i]) cnt++;
		return cnt>=3;
	}
};
cow a[20010];
unordered_map<int,int> mp;
int main()
{
	read(n);
	for(int i=1,x;i<=n;i++) read(x),a[i].x=x,a[i].pos[1]=i,mp[x]=i;
	for(int i=2,x;i<=5;i++) for(int j=1;j<=n;j++) read(x),a[mp[x]].pos[i]=j;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) write(a[i].x),write('\n');
	fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
	return 0;
}