P3034 [USACO11DEC] Cow Photography G/S

传送门题目描述今天的奶牛们特别调皮Farmer John 想做的只是给排成一排的奶牛拍照但是在他拍下照片之前奶牛们一直在移动。具体地说FJ 有N NN头奶牛1 ≤ N ≤ 20 000 1 \leq N \leq 20\,0001≤N≤20000每头奶牛都有一个唯一确定的编号。FJ 想要以一个特定的顺序拍下一张奶牛排成一排的照片这个顺序用数组A [ 1 … N ] A[1 \ldots N]A[1…N]表示其中A [ i ] A[i]A[i]代表排在i ii位置的奶牛的编号。他按照这样的顺序将奶牛们排列好但在他按下快门之前有些奶牛可能是零头或任意多头奶牛位置也不一定连续将移到一个新的位置。更准确地说一些奶牛离开队列剩下的奶牛靠拢这些离开的奶牛再将自己重新插入到队列中的任意位置不一定是他们之前的位置。FJ 感到非常沮丧他再次按照A AA数组的顺序重新安排了队列。但在他再次按下快门之前又有一些奶牛移动到了新的位置。就这样FJ 拍了五张照片。给出每张照片拍摄的内容即 FJ 按下快门时奶牛的顺序请你尝试推算出 FJ 最初为奶牛们排的顺序即A AA数组。由于可能有奶牛移动照片显示的顺序与原来的顺序可能有所不同。但是一头奶牛最多只会移动一次即如果一头奶牛在拍其中一张照片时移动了它在拍其他四张照片的时候都不会移动。当然由于其他奶牛也在移动它在不同照片中的顺序并不一定相同。输入格式第一行包含一个整数N NN。接下来5 N 5N5N行每N NN行描述了一张照片中各奶牛的顺序。每行包含一个奶牛的编号保证所有编号都是不超过10 9 10^9109的非负整数。输出格式输出N NN行每行一个整数A [ i ] A[i]A[i]即 FJ 最初为奶牛排好的顺序。输入输出样例 #1输入 #15 10 20 30 40 50 20 10 30 40 50 30 10 20 40 50 40 10 20 30 50 50 10 20 30 40输出 #110 20 30 40 50说明/提示样例解释FJ 拍的五张照片分别为10 20 30 40 5020 10 30 40 5030 10 20 40 5040 10 20 30 5050 10 20 30 40思路此题虽是蓝题但十分的水蓝就是水的颜色嘛。可以使用一个 map 来储存一头奶牛在每张照片中的位置再记下有哪些奶牛接着排序即可。排序规则因为一头奶牛最多只会移动一次所以当一头奶牛在3 33张及以上的照片出现在另一头奶牛之前那么它的原始顺序便在另一头奶牛之前。代码#includebits/stdc.husingnamespacestd;#defineintlonglongintn,ans[1000001];mapint,inta[1000001];boolcmp(intx,inty){intcnt0;for(inti1;i5;i)if(a[i][x]a[i][y])cnt;returncnt2;}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinn;for(inti1;i5;i)for(intj1;jn;j){intx;cinx;a[i][x]j;ans[j]x;}sort(ans1,ans1n,cmp);for(inti1;in;i)coutans[i]\n;return0;}