OI

【做题笔记】2018.1.23

今天刷了排序ex，学到了一些小技巧

注：以下排序为非STL的轮子写法。

P1093奖学金

这题主要牵涉到排序的依据。而这种排序依据可以通过写一个判断函数快速实现。判断函数的返回值就是两个元素按照这种判断依据排序的先后顺序，各种依据的处理就在函数中集中完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
typedef struct node{
    int ch,en,ma;
    int sum;
    int num;
}sn;

sn a[500]={0};
int cmp(sn a,sn b){
    if(a.sum>b.sum)return 1;
    if(a.sum<b.sum) return 0;
    if(a.ch>b.ch)return 1;
    if(a.ch<b.ch) return 0;
    if(a.num<b.num)return 1;
    return 0;
}
void qqsort(int l,int r){
    int i,j;
    sn t,mid;
    i=l;j=r;
    mid=a[(i+j)/2];
    do{
        while(cmp(a[i],mid))i++;
        while(cmp(mid,a[j]))j--;
        if(i<=j){
            t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;
            j--;
        }
    }while(i<=j);
    if(i<r)qqsort(i,r);
    if(l<j)qqsort(l,j);
}

int main(){
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].ch,&a[i].ma,&a[i].en);
        a[i].sum=a[i].ch+a[i].ma+a[i].en;
        a[i].num=i;
    }
    qqsort(1,n);
    for(i=1;i<=5;i++)
      printf("%d %d\n",a[i].num,a[i].sum);
    return 0;
}

其中的cmp就嵌入快排中实现排序。

另：typedef

1
2
3
4
typedef struct xxx{
        int data;
}nd;
nd a[1000];

P1583
此题关键理解题意，因为有点绕。

这题用了上面的方法就更快了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<stdio.h>
typedef struct node{
    int num;
    int w;
    int w2;
}nd;
nd a[20005]={0};
int e[15]={0};

int cmp(nd a,nd b){
    if(a.w!=b.w)return a.w>b.w;
    return a.num<b.num;
}

void qqsort(int l,int r){
    int i,j;
    nd mid,t;
    i=l;j=r;
    mid=a[(i+j)/2];
    do{
        while(cmp(a[i],mid))i++;
        while(cmp(mid,a[j]))j--;
        if(i<=j){
            t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;
            j--;
        }
    }while(i<=j);
    if(i<r)qqsort(i,r);
    if(l<j)qqsort(l,j);
}

int main(){
    int n,k,i;
    scanf("%d%d",&n,&k);
    for(i=1;i<=10;i++)
      scanf("%d",&e[i]);
    for(i=1;i<=n;i++){
      scanf("%d",&a[i].w);
      a[i].num=i;
    }
    qqsort(1,n);
    for(i=1;i<=n;i++)
      a[i].w+=e[(i-1)%10+1];
    
    qqsort(1,n);
    for(i=1;i<=k;i++)
      printf("%d ",a[i].num);
    return 0;
}

P1051
此题较水，排序都不用，模拟扫一遍找最大即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
struct node{
    char name[40];
    int num;
};
struct node max,now;
int main(){
    int n,i,sum=0,aver_sc,class_sc,isca,iswe,essay;
    int ca,we;
    scanf("%d",&n);
    max.num=0;
    for(i=1;i<=n;i++){
        now.num=0;
        scanf("%s",now.name);
        scanf("%d",&aver_sc);
        scanf("%d",&class_sc);
        getchar();
        scanf("%c",&ca);
        if(ca=='Y')isca=1;
        else isca=0;
        getchar();
        scanf("%c",&we);
        if(we=='Y')iswe=1;
        else iswe=0;
        scanf("%d",&essay);
        if(aver_sc>80&&essay>=1)now.num+=8000;
        if(aver_sc>85&&class_sc>80)now.num+=4000;
        if(aver_sc>90)now.num+=2000;
        if(aver_sc>85&&iswe)now.num+=1000;
        if(class_sc>80&&isca)now.num+=850;
        if(now.num>max.num)max=now;
        sum+=now.num;
       // printf("a:%d c:%d ca:%c we:%c e:%d name:%s\n",aver_sc,class_sc,ca,we,essay,now.name);
    }
    printf("%s\n%d\n%d\n",max.name,max.num,sum);
    return 0;
}