暑假D1 T2 play(加速排序)
标签:比较 amp for dig sort 相同 题目 getchar printf
题目大意
这个位面存在编号为1~2N的2N个斗士,他们正为争夺斗士大餐展开R轮PVP,每个斗士i都有一个固有APM ai,和一个初始斗士大餐储量 bi。每轮开始前以及最后一轮结束之后,2N个斗士会重新按照各自斗士大餐的储量进行排序(斗士大餐储量相同时编号小的靠前),每轮中,第1名和第2名PVP,第3名和第4名PVP,……第2k-1名和第2k名PVP,第2N-1名和第2N名PVP。而每场一对一的PVP都非常无聊,总是两个斗士中APM高的获胜,另一方失败;或者APM相同的两方取得平手。每轮赛后获胜方获得2份斗士大餐,平均双方均获得1份斗士大餐。
求输出最后排名从小到大的各斗士编号。
思路
最初很容易可以想到用快排之后,直接模拟就好,复杂度O(R*logn)
思考优化排序,将赢的、输的、平的分成三个队伍,对于每个队伍他bi增加的值相同,而一开始又有顺序,所以在队伍中仍有单调性。
需要注意的是,在顶端的人bi是比较小的,所以在重新确定p数组时需要倒序插入。
1 #include 2 using namespace std;
3
4 const int maxn=200005;
5 int n,r,q,top1,top2;
6 struct person{
7 int a,b,id;
8 }p[maxn],winner[maxn],loser[maxn];
9
10 templateclass T>inline void read(T &x){
11 x=0;char ch=getchar();
12 while(!isdigit(ch)) ch=getchar();
13 while(isdigit(ch)) {x=(x1)+(x3)+(ch^48);ch=getchar();}
14 }
15
16 bool cmp(person s,person t){
17 if(s.b==t.b) return s.idt.id;
18 return s.b>t.b;
19 }
20
21 bool cmp1(person s,person t){
22 if(s.b==t.b) return s.id>t.id;
23 return s.bt.b;
24 }
25
26 int main(){
27 scanf("%d%d%d",&n,&r,&q);
28 for(int i=1;i2*n;i++){
29 scanf("%d",&p[i].b);
30 p[i].id=i;
31 }
32 for(int i=1;i2*n;i++) scanf("%d",&p[i].a);
33 sort(p+1,p+2*n+1,cmp);
34 while(r--){
35 for(int i=1;i2*n;i+=2)
36 if(p[i].a>p[i+1].a){
37 p[i].b++;
38 winner[++top1]=p[i];
39 loser[++top2]=p[i+1];
40 }
41 else{
42 p[i+1].b++;
43 winner[++top1]=p[i+1];
44 loser[++top2]=p[i];
45 }
46 for(int i=2*n;i;i--){
47 if(top1){
48 if(top2){
49 if(cmp1(winner[top1],loser[top2])) p[i]=winner[top1--];
50 else p[i]=loser[top2--];
51 }
52 else p[i]=winner[top1--];
53 }
54 else p[i]=loser[top2--];
55 }
56 }
57 printf("%d",p[q].id);
58 return 0;
59 }
暑假D1 T2 play(加速排序)
标签:比较 amp for dig sort 相同 题目 getchar printf
原文地址:https://www.cnblogs.com/sto324/p/11160684.html
评论