NOIP 2011 普及组 第三题 瑞士轮

认真读题很重要

简单分析

---

题目链接:[https://www.luogu.org/problemnew/show/P1309]

很容易发现，这道题目考察的排序，排序我们第一个肯定想到的是sort或者是归并排序，的确时间复杂度分别是O(n log2(n) )与O(n log(n) )可如果是多次计算呢? 排除快排是因为不稳定性 所以总时间复杂度约为: sort O( r*2n^2*log2(2n) ) 归并 O( r*2n^2*log(2n) ) 看看数据范围emmmm 据说这样会 60 分,剩下的你懂的 所以我们需要优化 很显然sort已经没有优化的余地了，所以我们要从归并考虑 然后我们发现每次增减分的数组是单调的 也就是说我们只需要在开始的时候全部排序，后面我们每次只需要花O(n)的时间合并即可 这样子的时间复杂度约为:O( r*n^2 ) 稳如老狗啊!!!

代码

---

#include <cstdio>
#include <algorithm>
using namespace std;
int n,r,q;
struct node {
    int n,s,p;// n 号码 s 分数 p 能力
}a[210000],left[110000],right[110000];
int lcnt,rcnt,cnt,result_start;
// cmp 不解释
bool cmp(node a,node b){
    if(a.s==b.s) return a.n<b.n;
    else return a.s>b.s;
}
// 合并区间，参照归并排序
void marge(int left_start,int right_start){
    result_start=1;
    while(left_start<=n&&right_start<=n){
        if(cmp(left[left_start],right[right_start])) a[result_start++]=left[left_start++];
        else a[result_start++]=right[right_start++];
    }
    while(left_start<=n) a[result_start++]=left[left_start++];
    while(right_start<=n) a[result_start++]=right[right_start++];
}
int main(){
// 读入
    scanf("%d%d%d",&n,&r,&q);
    for(int i=1;i<=2*n;i++){scanf("%d",&a[i].s);a[i].n=i;}
    for(int i=1;i<=2*n;i++) scanf("%d",&a[i].p);
    sort(a+1,a+1+2*n,cmp);
    for(int i=1;i<=r;i++){
        lcnt=rcnt=0;// 模拟比赛过程
        for(int j=1;j<=2*n;j+=2){
            if(a[j].p>=a[j+1].p){
                a[j].s+=1;
                //printf("%d\n",++cnt);
                left[++lcnt]=a[j];right[++rcnt]=a[j+1];
            }
            else{
                a[j+1].s+=1;
                //printf("%d\n",++cnt);
                right[++rcnt]=a[j];left[++lcnt]=a[j+1];
            }
        }// 排序不解释
        if(i==1) sort(a+1,a+1+2*n,cmp);
        else marge(1,1);
    }
    printf("%d",a[q].n);
}

End

---

灵活运用每一种算法是一个非常重要的艺术 ]]>