P1309 [NOIP2011 普及组] 瑞士轮 归并算法

瑞士轮 归并算法"/>

P1309 [NOIP2011 普及组] 瑞士轮 归并算法

知识点：

1.归并算法的应用

2.自定义sort函数对结构体的排序

总思路：首先，初排序，根据排名两两比赛，分数变化，再排名，循环r次

坑：

1.结构体赋值考虑是 整体赋值 还是 分数 编号 的赋值

2.记录胜负的两组数组是int型还是自定义型

3.归并函数里 while的次数

代码如下

//归并使用在给分数排序的时候
#include<iostream>
#include<algorithm>using namespace std;int n,r,q;struct happy{int s,w,hao;
}a[200050],win[100010],lose[100010];bool cmp(happy x,happy y)
{if(x.s==y.s) return x.hao<y.hao;else return x.s>y.s;
}void dfs()
{n/=2;int i,j,b;i=j=b=1;while(i<=n&&j<=n){if(cmp(win[i],lose[j])) a[b++]=win[i++];else a[b++]=lose[j++];}while(i<=n) a[b++]=win[i++];while(j<=n) a[b++]=lose[j++];n*=2;
}int main()
{cin>>n>>r>>q;n*=2;for(int i=1;i<=n;i++) a[i].hao=i;for(int i=1;i<=n;i++) cin>>a[i].s;for(int i=1;i<=n;i++) cin>>a[i].w;    sort(a+1,a+n+1,cmp);//一次sort之后不再需要使用此函数——两个数组分别保存了while(r--){for(int i=1;i<=n;i+=2)if(a[i].w>a[i+1].w){a[i].s++;win[(i+1)/2]=a[i];lose[(i+1)/2]=a[i+1];}else{a[i+1].s++;win[(i+1)/2]=a[i+1];lose[(i+1)/2]=a[i];}dfs();}cout<<a[q].hao;return 0;
}