题目链接:https://www.luogu.com.cn/problem/P1309

如果是新手可能马上会想到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){//排序的时候判断大小(用标号)
 6      if(s[a]==s[b]){
 7          return a<b;
 8     }
 9       return s[a]>s[b];
10 }  
11 void Q(){//归并排序——并
12     int i,j;  
13     i=j=1,a[0]=0;  
14     while(i<=win[0]&&j<=lose[0]){//输赢两个有序序列,所以直接并
15         if(cmp(win[i],lose[j]))
16             a[++a[0]]=win[i++];//回到a(序号)数组  
17         else   
18             a[++a[0]]=lose[j++];
19     }    
20     while(i<=win[0])a[++a[0]]=win[i++];  
21     while(j<=lose[0])a[++a[0]]=lose[j++];//处理掉剩余的数       
22 }  
23 int main(){  
24     cin>>n>>r>>q;
25     n*=2;  
26     for(int i=1;i<=n;i++){
27         cin>>s[i];  
28     }
29     for(int i=1;i<=n;i++){
30         cin>>w[i];
31         a[i]=i;
32     }  
33     sort(a+1,a+n+1,cmp);//先快排一次 
34     for(int i=1;i<=r;i++){
35         win[0]=lose[0]=0;//0的正好没用,用来计数 
36         for(int j=1;j<=n;j+=2){
37             if(w[a[j]]>w[a[j+1]]){//判断哪方胜利
38                 s[a[j]]++;
39                 win[++win[0]]=a[j];
40                 lose[++lose[0]]=a[j+1];//加入
41             }  
42             else{
43                 s[a[j+1]]++; 
44                 win[++win[0]]=a[j+1];  
45                 lose[++lose[0]]=a[j];  
46             }
47         }    
48         Q();          
49     }
50     cout<<a[q];//结束
51     return 0;  
52 }

 

原文地址:http://www.cnblogs.com/wdrdsahudhisjabshdahuhsh/p/16818864.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性