奶牛摄影（春季每日一题 54）

奶牛们今天非常调皮。

农夫约翰想给站成一排的奶牛拍一张照片，但是在他有机会拍下照片之前，奶牛一直在移动。

具体的说，约翰有 $N$ 头奶牛，编号 $1\sim N$。

约翰想拍一张奶牛以特定顺序站成一排的照片，这个顺序可以用数组 $A[1..N]$ 来表示，其中 $A[j]$ 表示排列中第 $j$ 头奶牛的编号。

他按这个顺序将奶牛排成一排，但就在他按下相机上的按钮拍摄照片之前，最多一头奶牛移动到了新的位置上。

更准确地说，要么没有奶牛移动，要么一头奶牛离开她在队列中的当前位置，然后重新插入到队列中的新位置。

约翰非常沮丧，但并没有灰心，他再次按照数组 $A$ 的顺序，排列了他的奶牛。

但是，就在他再次拍照之前，又有最多一头奶牛移动到了队列中的新位置。

在约翰放弃之前，上面的过程一共重复了五次，拍下了五张照片。

给定每张照片的内容，请你推断出最初的预定顺序 $A$。

每张照片显示的都是在预定顺序下，最多一头奶牛移动后的奶牛排列顺序。

每头奶牛最多只会在拍摄一张照片时移动，如果一头奶牛在拍摄一张照片时移动了，那么她就不会在拍摄其他照片时主动移动。（尽管由于其他奶牛的移动，她最终可能会处于不同的位置）

输入格式
第一行包含整数 $N$，表示奶牛数量。

接下来 $5N$ 行，每 $N$ 行描述一张照片中的奶牛顺序，每行包含一个奶牛的编号。

输出格式
共 $N$ 行，输出预定顺序 $A$，每行输出一个奶牛编号。
可以证明，本题解唯一。

数据范围
$1\le N\le 20000$

输入样例：

5
1 
2 
3 
4 
5
2
1
3
4
5
3
1
2
4
5
4
1
2
3
5
5
1
2
3
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

输出样例：

1
2
3
4
5
1
2
3
4
5

---

另一种更简洁的排序方法，直接对奶牛进行排序，在 sort 时判断两个奶牛 5 次出现的位置的大小关系，如果一个奶牛出现的次数 3 次及以上比另一个奶牛小，说明这个奶牛在另一个奶牛的前面。

#include<iostream>
#include<algorithm>
#include<unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 20010;

int n;
unordered_map<int, vector<int>> mp;
PII res[N];

int main(){
    
    cin >> n;
    
    int t = 5, x;
    while(t--){
        
        for(int i = 0; i < n; i++){
            cin >> x;
            mp[x].push_back(i);
        }    
    }
    
    int k = 0;
    for(auto &p: mp){
        
        vector<int> v = p.y;
        sort(v.begin(), v.end());
        
        int s = 0;
        for(int x: v) s += x;
        
        if(abs(v[0] - v[2]) > 2) s -= v[0], s += v[1];
        if(abs(v[4] - v[2]) > 2) s -= v[4], s += v[1];
        
        res[k++] = {s, p.x};
    }
    
    sort(res, res + k);
    for(int i = 0; i < n; i++){
        cout << res[i].y << endl;
    }
    
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54