题目链接：点击打开链接
题目大意：给出 2*n 个人，每次第1个人和第2个人比赛，第3个人和第4个人比赛…进行 r 轮比赛，每轮比完赛都进行排名，求出最后第 q 名是谁。能力大的获胜，获胜的加 1分，输了的加 0分。
解题思路：归并排序思想，每轮比赛，把赢者放一组，输者放一组，这样单个数组t1/t2也是有序的，然后进行合并也能保证数组nds有序。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e5*2+10; int len; struct node { int id,score,power; }nds[maxn],t1[maxn],t2[maxn]; int cmp(node n1,node n2) { return n1.score==n2.score?n1.id<n2.id:n1.score>n2.score; } void mergeArr() { // printf("Before Merge :\n"); /* nds因为第一次sort过，所以接下来分别分为 胜利组t1 和 失败组t2 */ int k1=1,k2=1; for(int i=1;i<=len;i+=2) { if(nds[i].power>nds[i+1].power) nds[i].score++,t1[k1++]=nds[i],t2[k2++]=nds[i+1]; else nds[i+1].score++,t1[k1++]=nds[i+1],t2[k2++]=nds[i]; } // for(int i=1;i<k1;i++) // { // printf("%d ",t1[i].id); // } // puts(""); // for(int i=1;i<k1;i++) // { // printf("%d ",t1[i].score); // } // puts(""); // // for(int i=1;i<k2;i++) // { // printf("%d ",t2[i].id); // } // puts(""); // for(int i=1;i<k2;i++) // { // printf("%d ",t2[i].score); // } // puts(""); // // printf("After Merge :\n"); /* 胜利组t1 和 失败组t2 合并为nds，而且一定保证是有序的，节省了原生归并排序的mergeSort步骤 */ int i=1,j=1,k=1; while(i<k1&&j<k2) { if(t1[i].score>t2[j].score) nds[k++]=t1[i++]; else if(t1[i].score==t2[j].score) t1[i].id<t2[j].id ? nds[k++]=t1[i++] : nds[k++]=t2[j++]; else nds[k++]=t2[j++]; } while(i<k1) nds[k++]=t1[i++]; while(j<k2) nds[k++]=t2[j++]; // for(i=1;i<=len;i++) // { // printf("%d ",nds[i].id); // } // puts(""); // for(i=1;i<=len;i++) // { // printf("%d ",nds[i].score); // } // puts(""); } //void mergeSort(int first, int last) // TLE //{ // if(first<last) // { // int m=first+((last-first)>>1); // mergeSort(first,m); // mergeSort(m+1,last); // mergeArr(first,m,last); // } //} int main() { int T; scanf("%d",&T); int n,r,q; while(T-- && ~scanf("%d%d%d",&n,&r,&q)) { len=2*n; for(int i=1;i<=len;i++) { nds[i].id=i; scanf("%d",&nds[i].score); } for(int i=1;i<=len;i++) scanf("%d",&nds[i].power); sort(nds+1,nds+1+len,cmp); for(int i=1;i<=r;i++) { mergeArr(); } printf("%d\n",nds[q].id); } return 0; }
/
