题目链接: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. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性