AcWing 447. 瑞士轮 结构体版的归并排序
原题链接
简单
作者:
辉小歌
,
2021-05-25 09:38:55
,
所有人可见
,
阅读 356
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5*2+20;
struct student
{
long long int id,s,p;
}stu[N],a[N],b[N];
bool cmp(student a,student b)
{
if(a.s==b.s)
return a.id<b.id;
return a.s>b.s;
}
int main(void)
{
int n,r,q; cin>>n>>r>>q;
for(int i=1;i<=2*n;i++) cin>>stu[i].s,stu[i].id=i;
for(int i=1;i<=2*n;i++) cin>>stu[i].p;
sort(stu+1,stu+2*n+1,cmp);
while(r--)
{
int l=1,r=1;
for(int i=2;i<=2*n;i+=2)
{
if(stu[i-1].p>stu[i].p) stu[i-1].s++,a[l++]=stu[i-1],b[r++]=stu[i];
else stu[i].s++,a[l++]=stu[i],b[r++]=stu[i-1];
}
int i=1,j=1,k=1;
while(i<l&&j<r)
{
if(cmp(a[i],b[j])) stu[k++]=a[i++];
else stu[k++]=b[j++];
}
while(i<l) stu[k++]=a[i++];
while(j<r) stu[k++]=b[j++];
}
sort(stu+1,stu+2*n+1,cmp);
cout<<stu[q].id<<endl;
return 0;
}