洛谷 P1309 瑞士轮题解

野性酷女 2021-10-29 13:20 282阅读 0赞

每日一题 day4 打卡

### Analysis ###

暴力+快排（其实是归并排序）

一开始天真的以为sort能过，结果光荣TLE，由于每次只更改相邻的元素，于是善于处理随机数的快排就会浪费很多时间。于是就想到归并排序：归并排序的思想就是合

并两个同序数组的线性方式——每次比较两个有序数组指针指向的值，谁更小（大）则放到temp数组里，然后删掉进入temp的元素，指针++。然而我并没有实现，先把

快排水过的代码放上来，等有时间学归并排序了再来改。

1 #pragma GCC optimize(2)
     2 #include<iostream>
     3 #include<cstdio>
     4 #include<cstring>
     5 #include<algorithm>
     6 #define maxn 100000+10
     7 using namespace std;
     8 inline int read() 
     9 {
    10     int x=0;
    11     bool f=1;
    12     char c=getchar();
    13     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
    14     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    15     if(f) return x;
    16     return 0-x;
    17 }
    18 inline void write(int x)
    19 {
    20     if(x<0){putchar('-');x=-x;}
    21     if(x>9)write(x/10);
    22     putchar(x%10+'0');
    23 }
    24 int n,r,q; 
    25 struct node 
    26 {
    27     int num,s,w;
    28 }x[2*maxn];
    29 inline bool cmp(node a,node b)
    30 {
    31     if(a.s!=b.s) return a.s>b.s;
    32     else return a.num<b.num;
    33 }
    34 int main()
    35 {
    36     n=read();r=read();q=read();
    37     for(int i=1;i<=2*n;i++) x[i].num=i,x[i].s=read();
    38     for(int i=1;i<=2*n;i++) x[i].w=read();
    39     for(int i=1;i<=r;i++)
    40     {
    41         sort(x+1,x+2*n+1,cmp);
    42         for(int i=2;i<=2*n;i+=2)
    43         {
    44             if(x[i].w>x[i-1].w) x[i].s+=1;
    45             else if(x[i].w<x[i-1].w) x[i-1].s+=1;
    46         }
    47     }
    48     sort(x+1,x+2*n+1,cmp);
    49     write(x[q].num);
    50     return 0;
    51 }
    52

请各位大佬斧正（反正我不认识斧正是什么意思）

转载于:https://www.cnblogs.com/handsome-zyc/p/11355234.html