模拟赛考到的题,来发题解。
解法
因为题中说如果一头奶牛在拍其中一张照片时移动了,它在拍其他四张照片的时候都不会移动,所以设有两头奶牛 $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/
*/
};
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;
}