SYCOJ906瑞士轮
2021/7/13 6:07:41
本文主要是介绍SYCOJ906瑞士轮,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目—瑞士轮 (shiyancang.cn)
模拟题
#include<bits/stdc++.h> using namespace std; const int N=1e5+520; int n,r,q,res1=1,res2=1; struct grade { int total,num,abi; }a[N*4],win[N*4],lose[N*4]; bool cmp(grade x,grade y) { return x.total>y.total||x.total==y.total&&x.num<y.num; } void merge_sort(int res1,int res2) { int l=1,w=1,cnt=1; while(l<res1&&w<res2) { if(cmp(win[l],lose[w])) a[cnt++]=win[l++]; else a[cnt++]=lose[w++]; } while(l<res1) a[cnt++]=win[l++]; while(w<res2) a[cnt++]=lose[w++]; } int main() { scanf("%d%d%d",&n,&r,&q); for(int i=1;i<=n*2;i++) scanf("%d",&a[i].total); for(int i=1;i<=n*2;i++) scanf("%d",&a[i].abi),a[i].num=i; sort(a+1,a+1+n*2,cmp); // for(int i=1;i<=n*2;i++) cout<<a[i].total<<" "; // puts(""); while(r--) { res1=1,res2=1; for(int i=1;i<=n;i++) { if(a[i*2-1].abi>a[i*2].abi) a[i*2-1].total++,win[res1++]=a[i*2-1],lose[res2++]=a[i*2]; else a[i*2].total++,win[res1++]=a[i*2],lose[res2++]=a[i*2-1]; } // sort(a+1,a+1+n*2,cmp); 卡sort // for(int i=1;i<=n*2;i++) cout<<a[i].total<<' '; // puts(""); // for(int i=1;i<=n*2;i++) cout<<a[i].num<<' '; // puts(""); merge_sort(res1,res2); } cout<<a[q].num<<'\n'; return 0; }
如果是每次用sort会超时。
这题是一道归并题,记录每一次的win and lose ,因为本身按照排名来算的,那么其本身就是有序的,所以完全可以在o(n)内完成操作,每次的名次在比完直接可以知道,那么直接按照归并双指针合并即可。
这篇关于SYCOJ906瑞士轮的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解