本文作者:Zhang, Xuheng 本文分类:编程学习笔记 浏览:241
阅读时间:1108字, 约1-2分钟



经典的瑞士轮,这道题一开始第一个思路就是每轮进行操作然后sort一遍
不过要是这样子,数据会让你刚好T掉
所以我们需要常数优化
怎么优化呢?
首先可以看到每轮操作后每个选手分数要么+1,要么不变
于是愉快的使用归并排序
代码如下:
#include <cstdio> #include <cstdlib> #include <cmath> #include <iostream> #include <cstring> #include <ctime> #include <algorithm> #include <queue> #include <map> #define ci const int #define ri register int #define ll long long #define reg register #define boom return #define cmax(a,b) (a)>(b)?(a):(b) #define cmin(a,b) (a)<(b)?(a):(b) #define For(i,a,b) for(i=a;i<b;i++) using namespace std; ci MAXN=200086; struct Player { int num,s,w; }a[MAXN],b[MAXN],ans[MAXN]; int n,r,q; bool pd(Player a,Player b) {return (a.s==b.s)?(a.num<b.num):(a.s>b.s);} void solve() { int x=1,y=1,z; for (z=1;z<=n*2;z+=2) if (ans[z].w>ans[z+1].w)ans[z].s++,a[x++]=ans[z],b[y++]=ans[z+1]; else ans[z+1].s++,a[x++]=ans[z+1],b[y++]=ans[z]; int i=1,j=1,k=1; while(i<x&&j<y) if(pd(a[i],b[j]))ans[k++]=a[i++]; else ans[k++]=b[j++]; while(i<x)ans[k++]=a[i++]; while(j<y)ans[k++]=b[j++]; } int main() { int i; scanf("%d%d%d",&n,&r,&q); for(i=1;i<=n*2;i++) scanf("%d",&ans[i].s),ans[i].num=i; for (i=1;i<=n*2;i++)scanf("%d",&ans[i].w); sort(ans+1,ans+1+2*n,pd); for (i=1;i<=r;i++)solve(); printf("%d\n",ans[q].num); return 0; }
关于作者Zhang, Xuheng
- 还没有填写个人简介
- Email: hy23682@126.com
- 注册于: 2020-04-07 05:11:14
主题操作记录
2020.5.8 13:44 审核通过