题解 P3034 【[USACO11DEC]牛摄影Cow Photography】

我们可以发现，如果一头牛在三张照片中在另一头牛的前面，那么它在原生序列中就在另一头牛的前面，__因为一头牛只有一次机会在一张照片中改变自己和另一头牛的相对位置，在下一张照片中就必须要回去__。 所以代码就很好写了,我们用```map```记录每头牛在每一张照片中的位置，然后给任意一张照片排序，比较的时候就按上文的方法就可以了: ```cpp #include<bits/stdc++.h> #include<tr1/unordered_map> using namespace std; tr1::unordered_map<int,int>ma[6];//O(1)复杂度的map bool cmp(int x,int y){ int num=0; for(int i=1;i<=5;i++){ if(ma[i][x]<ma[i][y])num++; } return num>=3; } int a[20001]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=5;i++) for(int j=1;j<=n;j++){ int x; scanf("%d",&x); a[j]=x; ma[i][x]=j; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++){ printf("%d\n",a[i]); } return 0; } ```