2011年Noip普及组第三题解析

本文作者：Zhang, Xuheng  本文分类：编程学习笔记  浏览：241
阅读时间：1108字, 约1-2分钟

经典的瑞士轮，这道题一开始第一个思路就是每轮进行操作然后sort一遍
不过要是这样子，数据会让你刚好T掉
所以我们需要常数优化
怎么优化呢？
首先可以看到每轮操作后每个选手分数要么+1，要么不变
于是愉快的使用归并排序

代码如下：

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <queue>
#include <map>
#define ci const int
#define ri register int
#define ll long long
#define reg register
#define boom return 
#define cmax(a,b) (a)>(b)?(a):(b)
#define cmin(a,b) (a)<(b)?(a):(b)
#define For(i,a,b) for(i=a;i<b;i++)
using namespace std;
ci MAXN=200086;
struct Player
{  
    int num,s,w;  
}a[MAXN],b[MAXN],ans[MAXN];  
int n,r,q;  
bool pd(Player a,Player b)
{return (a.s==b.s)?(a.num<b.num):(a.s>b.s);}  
void solve()
{
    int x=1,y=1,z;  
    for (z=1;z<=n*2;z+=2)  
        if (ans[z].w>ans[z+1].w)ans[z].s++,a[x++]=ans[z],b[y++]=ans[z+1];
        else ans[z+1].s++,a[x++]=ans[z+1],b[y++]=ans[z];    
    int i=1,j=1,k=1;  
    while(i<x&&j<y)  
        if(pd(a[i],b[j]))ans[k++]=a[i++];
        else ans[k++]=b[j++]; 
    while(i<x)ans[k++]=a[i++];  
    while(j<y)ans[k++]=b[j++];  
}  
int main()
{  
	int i;
	
    scanf("%d%d%d",&n,&r,&q);  
    for(i=1;i<=n*2;i++)  
        scanf("%d",&ans[i].s),ans[i].num=i;  
    for (i=1;i<=n*2;i++)scanf("%d",&ans[i].w);  
    sort(ans+1,ans+1+2*n,pd);  
    for (i=1;i<=r;i++)solve();
    printf("%d\n",ans[q].num);  
    return 0;  
}

关于作者Zhang, Xuheng

• 还没有填写个人简介
• Email: hy23682@126.com
• 注册于: 2020-04-07 05:11:14