[NOIP·2011普及组] 瑞士轮 - jiandanset - 博客园

#include

#include

using namespace std;

struct P{

int num,s,w;

};

int n,r,q;

P a[200002],b[200002],ans[200002];//ans存每一轮比赛后的结果，按名次来排，要归并，总得有两个有序的数组，所以就拿a来存赢的，b来存输的，至于为什么a，b有序，上面已经说过了

bool pcmp(const P& a,const P& b) {

return (a.s==b.s)?(a.numb.s);//注意特殊情况的处理

}

void solve() {//每调用一次solve(),就会求出下一轮的比赛结果，所以主程序中调用了r次来求出r轮后的结果

int ai=1,bi=1;

for (int i=1;i<=n*2;i+=2) {

if (ans[i].w>ans[i+1].w)

{

ans[i].s++;

a[ai++]=ans[i];

b[bi++]=ans[i+1];

}

else {

ans[i+1].s++;

a[ai++]=ans[i+1];

b[bi++]=ans[i];

}

}

int i=1,j=1,k=1;

while (i

if (pcmp(a[i],b[j])) {

ans[k++]=a[i++];

}

else {

ans[k++]=b[j++];

}

}

while (i

while (j

}

int main() {

scanf("%d%d%d",&n,&r,&q);

n*=2;

for (int i=1;i<=n;i++) {

scanf("%d",&ans[i].s);

ans[i].num=i;

}

for (int i=1;i<=n;i++) {

scanf("%d",&ans[i].w);

}

sort(ans+1,ans+1+n,pcmp);//这里用快排效率高，一开始是一个随机数列

for (int i=1;i<=r;i++) {

solve();

}

printf("%d

",ans[q].num);

return 0;

}