問題 D: Cow Photography

• Line 1: The number of cows, N (1 <= N <= 20,000).

• Lines 2..5N+1: The next 5N lines describe five orderings, each one a block of N contiguous lines. Each line contains the ID of a cow, an integer in the range 0...1,000,000,000.

  輸出

• Lines 1..N: The intended ordering A, one ID per line.

  樣例輸入 Copy

  5

  10

  20

  30

  40

  50

  樣例輸出 Copy

  提示

  There are 5 cows, with IDs 10, 20, 30, 40, and 50. In each of the 5 photos, a different cow moves to the front of the line (at most one cow moves in each photo here, but it is possible in other inputs that multiple cows could move in a particular photo).The correct original ordering A[1..5] is 10, 20, 30, 40, 50.

  思路:如果有三次或者三次以上的照片中這個奶牛在另一個奶牛的前面, 那麼在正确的位置上這個奶牛也在這頭牛的前面

#include<iostream>
 #include<unordered_map>
 #include<algorithm>
 using namespace std;
 unordered_map<int, int> mp[6];
 const int N = 1e5 + 10;
int a[N], n;
 bool cmp(int a, int b)
 {
     int x = 0;
     for(int i = 1; i <= 5; i ++)
     {
        if(mp[i][a] < mp[i][b])x ++;
     }
     return x >= 3;
 }
 int main()
 {
     ios::sync_with_stdio(false);

     cin >> n;
     for(int i = 1; i <= 5; i ++)
     {
         for(int j = 1; j <= n; j ++)
         {
             cin >> a[j];
             mp[i][a[j]] = j; 
         }
     }
     sort(a + 1, a + 1 + n, cmp);
     for(int i = 1; i <= n; i ++)
     cout << a[i] << ' ';
     cout << endl;
     return 0;
 }