1. 首頁 > 生活百科 > >

0025：2011年NOIp普及組真題——瑞士輪題解

生活百科

題目鏈接：https://www.luogu.com.cn/problem/P1309
【0025：2011年NOIp普及組真題——瑞士輪題解】如果是新手可能馬上會想到sort排序，每比一次就排一次，但是這樣的時間復雜度有點高，只有60分；
這是因為每次比完賽會產生兩個有序數列（輸/贏），只需要把這兩個有序數列合并成一個有序數列，而sort則是排了所有的數，顯然浪費了時間
一提到有序數列，會想到歸并排序——由于兩個有序數列是現成的，所以只要并就行了，省了不少時間，可以AC
上代碼：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,r,q; 4 int a[200100],s[200100],w[200100],win[200100],lose[200100];//a——序號，s——分數，w——戰力 5 bool cmp(int a,int b){//排序的時候判斷大?。ㄓ帽旰牛? 6if(s[a]==s[b]){ 7return a<b; 8} 9return s[a]>s[b];10 }11 void Q(){//歸并排序——并12int i,j;13i=j=1,a[0]=0;14while(i<=win[0]&&j<=lose[0]){//輸贏兩個有序序列，所以直接并15if(cmp(win[i],lose[j]))16a[++a[0]]=win[i++];//回到a（序號）數組17else18a[++a[0]]=lose[j++];19}20while(i<=win[0])a[++a[0]]=win[i++];21while(j<=lose[0])a[++a[0]]=lose[j++];//處理掉剩余的數22 }23 int main(){24cin>>n>>r>>q;25n*=2;26for(int i=1;i<=n;i++){27cin>>s[i];28}29for(int i=1;i<=n;i++){30cin>>w[i];31a[i]=i;32}33sort(a+1,a+n+1,cmp);//先快排一次34for(int i=1;i<=r;i++){35win[0]=lose[0]=0;//0的正好沒用，用來計數36for(int j=1;j<=n;j+=2){37if(w[a[j]]>w[a[j+1]]){//判斷哪方勝利38s[a[j]]++;39win[++win[0]]=a[j];40lose[++lose[0]]=a[j+1];//加入41}42else{43s[a[j+1]]++;44win[++win[0]]=a[j+1];45lose[++lose[0]]=a[j];46}47}48Q();49}50cout<<a[q];//結束51return 0;52 }

    推薦閱讀