题意解析

有$2*n$名选手，每名选手有各自的初试分数和实力。 现进行$r$场比赛，相邻两名选手进行比拼，实力强者分数加一。 求最后第$q$名是谁。

思路解析

运用结构体排序模拟比赛，得60分

优化

可以发现，每次排序都十分耗时，但胜者和败者相对位置不变，所以可以用归并排序快速排序。

#include<bits/stdc++.h>
using namespace std;
long long n,r,q;
struct P{
	long long x,d,w;
};
P s[200100],a[100100],b[100100];
bool cmp(P a1,P a2){
	if(a1.x==a2.x)return a1.d<a2.d;
	else return a1.x>a2.x;
}
long long tt(long long x,long long y){
	long long res=1;
	for(int i=1;i<=y;i++)res*=x;
	return res;
}
int main(){
	//freopen("ruishi.in","r",stdin);
	//freopen("ruishi.out","w",stdout);
	cin>>n>>r>>q;
	cout<<tt(n,r);
	for(int i=1;i<=2*n;i++){
		cin>>s[i].x;
		s[i].d=i;
	}
	for(int i=1;i<=2*n;i++)cin>>s[i].w;
	sort(s+1,s+2*n+1,cmp);
	for(int i=1;i<=r;i++){
		long long d1=1,d2=1,d3=1;
		for(int j=1;j<2*n;j+=2){
			if(s[j].w>s[j+1].w){
				s[j].x++;
				a[d1++]=s[j];
				b[d2++]=s[j+1];
			}
			else{
				s[j+1].x++;
				a[d1++]=s[j+1];
				b[d2++]=s[j];
			}
		}
		d1=1,d2=1;
		while(d1<=n and d2<=n){
			if(cmp(a[d1],b[d2]))s[d3++]=a[d1++];
			else s[d3++]=b[d2++];
		}
		while(d1<=n)s[d3++]=a[d1++];
		while(d2<=n)s[d3++]=b[d2++];
		for(int i=1;i<=2*n;i++)cout<<s[i].d<<endl;
	}
}