洛谷 1309

• 题意：题意见上图，很明确，纯暴力可以做出来正确结果，但是会出现超时情况。
• 思路：①😅纯纯的想法是，将这些数据封装成一个结构体，然后进行r次排序，比较，最后输出即可，😒不过这样太暴力，不可取。②😏改进的方法是，洛谷题解的好想法。就是每次pk完后，🙂分成两拨，一波是赢家，一波是输家。每一次比赛后合并。附上链接。

#include<bits/stdc++.h>

using namespace std;

const int M = 2e5+5;
int n,r,q;

typedef struct A{
	int g,no,w; //得分、编号、实力值 
}Node;

int aL,wL,lL;
Node all[M],win[M],lose[M];

bool cmp(Node a,Node b){
	if(a.g!=b.g) return a.g > b.g;
	return a.no < b.no;
}

void merge(){
	int i=1,j=1;
	aL = 0;
	while(i<=wL && j<=lL){
		if(cmp(win[i],lose[j])) all[++aL] = win[i++];
		else all[++aL] = lose[j++];
	}
	while(i<=wL) all[++aL] = win[i++];
	while(j<=lL) all[++aL] = lose[j++];
}

int main()
{
	std::ios::sync_with_stdio(false);
    cin.tie(0);
	cin >> n >> r >> q;
	for(int i=1;i<=2*n;i++){
		cin >> all[i].g;
		all[i].no = i;
	}
	for(int i=1;i<=2*n;i++){
		cin >> all[i].w;
	}
	
	sort(all+1,all+1+2*n,cmp);
	while(r--){
		wL = lL = 0;
		for(int i=1;i<2*n;i+=2){
			if(all[i].w>all[i+1].w){
				all[i].g++;
				win[++wL] = all[i];
				lose[++lL] = all[i+1];
			}else{
				all[i+1].g++;
				win[++wL] = all[i+1];
				lose[++lL] = all[i];
			}
		}
		merge();
	}
	cout << all[q].no << endl;
    
	return 0;
}