牛客多校第六場 Singing Contest

連結：https://www.nowcoder.com/acm/contest/144/A

來源：牛客網

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 262144K，其他語言524288K

64bit IO Format: %lld

題目描述

Jigglypuff is holding a singing contest. There are 2n singers indexed from 1 to 2n participating in the contest.

The rule of this contest is like the knockout match. That is, in the first round, singer 1 competes with singer 2, singer 3 competes with singer 4 and so on; in the second round, the winner of singer 1 and singer 2 competes with the winner of singer 3 and singer 4 and so on. There are n rounds in total.

Each singer has prepared n songs before the contest. Each song has a unique pleasantness. In each round, a singer should sing a song among the songs he prepared. In order not to disappoint the audience, one song cannot be performed more than once. The singer who sings the song with higher pleasantness wins.

Now all the singers know the pleasantness of songs prepared by all the others. Everyone wants to win as many rounds as he can. Assuming that singers choose their song optimally, Jigglypuff wants to know which singer will win the contest?

輸入描述:

The input starts with one line containing exactly one integer t which is the number of test cases. (1 ≤ t ≤ 10)

For each test case, the first line contains exactly one integer n where 2n is the number of singers. (1 ≤ n ≤ 14)

Each of the next 2n lines contains n integers where aij is the pleasantness of the j-th song of the i-th singer. It is guaranteed that all these 2nx n integers are pairwise distinct. (1 ≤ aij ≤ 109)      

輸出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x is the test case number (starting from 1) and y is the index of the winner.      

示例1

輸入

2
1
1
2
2
1 8
2 7
3 4
5 6
      

輸出

Case #1: 2
Case #2: 4      

題意：有2^n個選手，每個選手有n首歌，每首歌都有不同的愉悅值，這些歌手經過n回合的比賽，每輪比賽1,2；3,4；…………

号的歌手比賽，每個人選擇一首歌，誰的歌的愉悅值高，誰獲勝，獲勝者進入下一輪，若采取最優政策，問最終獲勝者是誰；

思路：用隊列模拟即可；

下面附上我的代碼：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#define long long LL
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define lson o<<1
#define rson o<<1|1
using namespace std;
struct node{
	int a[20];
	int num;
}s[20005];
queue<node> q;
int main()
{
	int t, n, r = 0;
	cin >> t;
	while(t--)
	{
		while(!q.empty())
			q.pop(); 
		scanf("%d", &n);
		int k = pow(2, n);
		for(int i = 0; i < k; i++)
		{
			for(int j = 0; j < n; j++)
			{
				scanf("%d", &s[i].a[j]);	
			}
			sort(s[i].a, s[i].a + n);
			s[i].num = i;
			q.push(s[i]); 
		}
		while(!q.empty())
		{
			if(q.size() == 1)
				break;
			node p1 = q.front();
			q.pop();
			node p2 = q.front();
			q.pop();
			if(p1.a[n-1] > p2.a[n - 1])
			{
				int k = upper_bound(p1.a, p1.a + n, p2.a[n-1]) - p1.a;
				p1.a[k] = 0;
				sort(p1.a, p1.a + n);
				q.push(p1); 
			}
			else {
				int g = upper_bound(p2.a, p2.a + n, p1.a[n-1]) - p2.a;
				p2.a[g] = 0;
				sort(p2.a, p2.a + n);
				q.push(p2); 
			}
		}
		node v = q.front();
		printf("Case #%d: %d\n", ++r, v.num + 1);
	}
    return 0;
}