快排($RNlog^N$ 60pts)

• 进行瑞士轮模拟，每次比较以后调用快速排序规则进行排序。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct Node{
    int sc;
    int w;
    int id;
}s[N],q1[N],q2[N];
bool cmp(Node a,Node b) //排序规则
{
    if(a.sc>b.sc) return 1;
    if(a.sc==b.sc&&a.id<b.id) return 1;
    return 0;
}
int main()
{
    int n,r,q;
    cin>>n>>r>>q;
    for(int i=1;i<=2*n;i++) cin>>s[i].sc;
    for(int i=1;i<=2*n;i++)
    {
        cin>>s[i].w;
        s[i].id=i;
    }
    sort(s+1,s+2*n+1,cmp); //排序
    while(r--)
    {
        for(int i=1;i<=2*n;i+=2) //按照瑞士轮规则进行比较
        {
            if(s[i].w>s[i+1].w)
            {
                s[i].sc++;
            }
            else
            {
                s[i+1].sc++;
            }
        }
        sort(s+1,s+2*n+1,cmp); //比较完了以后重新排名
    }
    cout<<s[q].id;
    return 0;
}

快排+归并($NlogN+RN$)

• 首轮进行快速排序，然后在后面模拟瑞士轮的时候进行胜者组和败者组，然后对胜者组和败者组进行归并排序的归并过程。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct Node{ //结构体
    int sc;
    int w;
    int id;
}s[N],q1[N],q2[N]; //q1为胜者组,q2为败者组
bool cmp(Node a,Node b) //排序
{
    if(a.sc>b.sc) return 1;
    if(a.sc==b.sc&&a.id<b.id) return 1;
    return 0;
}
int main()
{
    int n,r,q;
    cin>>n>>r>>q;
    for(int i=1;i<=2*n;i++) cin>>s[i].sc;
    for(int i=1;i<=2*n;i++)
    {
        cin>>s[i].w;
        s[i].id=i;
    }
    sort(s+1,s+2*n+1,cmp); //首轮排序
    while(r--)
    {
        int x=0,y=0; //生成组和败者组初始化
        for(int i=1;i<=2*n;i+=2) //模拟瑞士轮
        {
            if(s[i].w>s[i+1].w)
            {
                s[i].sc++;
                q1[++x]=s[i];
                q2[++y]=s[i+1];
            }
            else
            {
                s[i+1].sc++;
                q1[++x]=s[i+1];
                q2[++y]=s[i];
            }
        }
        x=1,y=1; //开始合并
        int k=1;
        while(x<=n&&y<=n) //合并
        {
            if(cmp(q1[x],q2[y]))
            {
                s[k++]=q1[x++];
            }
            else s[k++]=q2[y++];
        }
        while(x<=n) s[k++]=q1[x++]; //合并剩余的胜者组
        while(y<=n) s[k++]=q2[y++]; //合并剩余的败者组
    }
    cout<<s[q].id;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct Participator{
	int score,force,id;
}p[N];
bool cmp(Participator x,Participator y)
{
	if(x.score>y.score) return true;
	return false;
}
int main()
{
	int n,r,q;
	cin>>n>>r>>q;
	for(int i=1;i<=n*2;i++)
	{
		cin>>p[i].score; 
	}
	for(int i=1;i<=n*2;i++)
	{
		cin>>p[i].force;
		p[i].id=i;
	}
	sort(p+1,p+2*n+1,cmp);
	while(r--)
	{
		vector<Participator> winner,loser;
		for(int i=1;i<=2*n;i+=2)
		{
			if(p[i].force>p[i+1].force)
			{
				p[i].score++;
				winner.push_back(p[i]);
				loser.push_back(p[i+1]);
			}
			else
			{
				p[i+1].score++;
				winner.push_back(p[i+1]);
				loser.push_back(p[i]);
			}
		}
		int cnt=1,cnt1=0,cnt2=0;
		while(cnt1<n&&cnt2<n)
		{
			if(winner[cnt1].score>loser[cnt2].score)
			{
				p[cnt++]=winner[cnt1];
				cnt1++;
			}
			else 
			{
				p[cnt++]=loser[cnt2];
				cnt2++;
			}
		}
		while(cnt1<n)
		{
			p[cnt++]=winner[cnt1];
			cnt1++; 
		}
		while(cnt2<n)
		{
			p[cnt++]=loser[cnt2];
			cnt2++; 
		} 
	}
	cout<<p[q].id;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e8+10;
int n,r,q;
struct PII{
	int li;
	int x;
	int i;
}a[N];
void run(PII x,PII y){
	if(x.li>y.li) x.x++;
	else y.x++;
}
bool Sort(PII x,PII y){
	if(x.x>y.x) return 1;
	if(x.x==y.x && x.i<y.i) return 1;
	return 0;
}
int main(){
	cin>>n>>r>>q;
	n*=2;
	for(int i=1;i<=n;i++){
		cin>>a[i].x;
		a[i].i=i;
	}
	for(int i=1;i<=n;i++) cin>>a[i].li;
	sort(a+1,a+1+n,Sort);
	while(r--){
		for(int i=1;i<=n;i+=2) run(a[i],a[i+1]);
		sort(a+1,a+1+n,Sort);
	}
	cout<<a[q].i;
    return 0;
}