题目链接： https://www.nowcoder.com/acm/contest/144/A
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.
Case #1: 2 Case #2: 4
题意：首先输入测试样例组数t，接下来输入n，代表我们接下来要进行n轮比赛，每场比赛相邻的两个人进行比赛，也就是1号与2号比，2号与3号比，一轮过后，1,2的获胜方与3,4的获胜方比赛，以此类推，进
行n轮最初就需要2^n个人，每个人都有可能进行n轮比赛之后获得冠军，于是每个人准备了n首歌，每首歌有自己的愉悦值，比赛时，愉悦值高的一定会战胜愉悦值低的。问最后谁会获得冠军。
做法：我们拿1,2比赛为例，假设现在1号不用出自己最大的愉悦值的歌曲，那么有可能2号就有比我愉悦值高的歌曲，此时这一轮我就输了，留着愉悦值高的歌也没有用了，于是，每一次，我们其中一方就要用出
自己最大的愉悦值的歌曲，如果1号愉悦值最高的歌曲的愉悦值大于2的，那么此时1号一定可以赢得这一轮，2号一定要用自己愉悦值最高的歌曲，1号不一定要用自己愉悦值最高的歌曲，只要二分出来比2号的高
就可以，于是，此题用vector可写，并且不断维护现在的入围选手都是第几号即可。
代码如下：
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> using namespace std; const int maxn = 20004; vector<int>V[maxn]; int ans[maxn] , len; ///记录此时每一名都是谁 以及现在还剩多少人 ///每个人每次都拿出来最大的与对手打 能打过就找到恰好大于对手最大值的去打 打不过就输了 直接淘汰 void init(int n) { for(int i=1; i<=n; i++) { V[i].clear(); ans[i] = i; ///刚开始有n个人 第i名就是第i个人 } } int poww(int a , int b) { int res = 1; for(int i=1; i<=b; i++) { res *= a; } return res; } void input(int n , int nn) { int tmp; for(int i=1; i<=n; i++) { for(int j=1; j<=nn; j++) { scanf("%d" , &tmp); V[i].push_back(tmp); } sort(V[i].begin() , V[i].end()); ///没有sort所以错了 } } void bi_sai(int x , int y , int num) { // printf("%d..%d..%d..%d..%d..........\n" , x , y , V[x].size() , V[y].size() , num); ///题目保证了不会有相同的愉悦值出现 int L = V[x].size(); if(V[x][L-1] > V[y][L-1]) { int pos = upper_bound(V[x].begin() , V[x].end() , V[y][L-1])-V[x].begin(); ans[num] = x; V[x].erase(V[x].begin()+pos); } else { int pos = upper_bound(V[y].begin() , V[y].end() , V[x][L-1])-V[y].begin(); ans[num] = y; V[y].erase(V[y].begin()+pos); } } void solve(int nn) { // printf("%d..%d..++++\n" , nn , len); for(int i=1; i<=nn; i++) ///一共要打n场 { for(int j=1; j<=len; j+=2) ///每一场是len个人比赛 第ans[i]个人和第ans[i+1]个人 { int a , b; a = ans[j]; b = ans[j+1]; // printf("%d/.%d..\n" , a , b); bi_sai(a , b , j/2+1); ///a 和 b比赛 赢了的获得第j/2+1名 // printf("%d...\n" , ans[j/2+1]); // printf("%d...%d..%d..\n" , i , j , len); } len /= 2; // printf("%d+++++++\n" , len); // for(int j=1; j<=len; j++) // { // printf("%d..\n" , ans[j]); // } } } void debug1(int n) { for(int i=1; i<=n; i++) { printf("%d..%d..\n" , i , V[i].size()); for(int j=0; j<V[i].size(); j++) { printf("%d " , V[i][j]); } printf("\n"); } } int main() { // printf("%d..\n" , poww(2 , 14)); int t , n , nn; scanf("%d" , &t); for(int cas=1; cas<=t; cas++) { scanf("%d" , &n); nn = n; n = poww(2 , n); len = n; init(n); input(n , nn); // debug1(n); solve(nn); printf("Case #%d: %d\n" , cas , ans[1]); } return 0; } /* 10 3 1 2 5 2 3 4 3 4 5 1 2 4 6 7 6 8 2 3 0 1 2 1 3 1 这个样例不好 出现了相等的情况 */
牛客网暑期ACM多校训练营（第六场） A Singing Contest
原文：https://www.cnblogs.com/Flower-Z/p/9648946.html