抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

算法题解(1)-排序

题解

排序

算法

发布于：2020年12月11日

字数：2.3k 字

时长：13 分钟

排序（c++）

虽然是c++，其实是c语法

洛谷P1271 选举学生会

已经得知了数据范围，使用桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int num;
    int bucket[n+1];
    for (int i = 0; i < n+1; ++i) {
        bucket[i] = 0;
    }
    for (int i = 0; i < m; ++i) {
        scanf("%d", &num);
        bucket[num] += 1;
    }

    for (int i = 0; i < n+1; ++i) {
        for (int j = 0; j < bucket[i]; ++j) {
            printf("%d ",i);
        }
    }
}

洛谷P1923 找出第k小的数

练习快排和分治

判断排序后两边数组长度，选择一边进行递归

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
#include <cstdlib>
#include <cstdio>
#include <ctime>

// 注意题目中最小数序号是0
void swap(int *a,int *b){
    int t=*a;
    *a=*b;
    *b=t;
}

int findi_quicksort(int arr[],int len,int index){
    if (len<=1) return arr[0];
    srand((unsigned)time(NULL));
    const int temp = arr[rand() % len];
    int i=0,j=0,k=len;
    while (i<k){
        if (arr[i] < temp){
            swap(&arr[i], &arr[j]);
            i++;j++;}
        else if (temp < arr[i]){
            swap(&arr[i], &arr[k-1]);
            k--;}
        else
            i++;
    }
    if (index<j) return findi_quicksort(arr, j,index);
    else if (index>=k) return findi_quicksort(arr + k, len - k,index-k);
    else return temp;
}

int main(){
    int n,i;
    scanf("%d%d",&n,&i);
    int number[n];
    for (int j = 0; j < n; ++j) {
        scanf("%d",&number[j]);
    }
    printf("%d",findi_quicksort(number,n,i));
}

洛谷P1059 明明的随机数

数据范围不大，可以用桶排序

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
#include <cstdio>

int bucket[1001];

int main() {
    int n;
    scanf("%d", &n);
    int number;
    for (int &i : bucket) {
        i = 0;
    }
    for (int i = 0; i < n; ++i) {
        scanf("%d", &number);
        bucket[number]++;
    }
    int count = 0;
    for (int i = 0; i < 1001; ++i) {
        if (bucket[i] > 0) {
            count++;
        }
    }
    printf("%d\n",count);
    for (int i = 0; i < 1001; ++i) {
        if (bucket[i] > 0) { 
            count++;
            printf("%d ", i);
        }
    }
}
P1059重新想了一下，也可以用快排

排序完后检测重复然后跳过就可以了

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
#include <cstdlib>
#include <cstdio>
#include <ctime>

void swap(int*a,int*b){
    int t=*a;
    *a=*b;
    *b=t;
}

void quicksort(int arr[],int len){
    if (len<=1) return;
    srand((unsigned)time(NULL));
    const int temp = arr[rand() % len];
    int i=0,j=0,k=len;
    while (i<k){
        if (arr[i]<temp){
            swap(&arr[i],&arr[j]);
            j++;
            i++;
        } else if(temp<arr[i]){
            swap(&arr[i],&arr[k-1]);
            k--;
        } else i++;
    }
    quicksort(arr,j);
    quicksort(arr+k,len-k);
}
int main(){
    int n;
    scanf("%d",&n);
    int number[n+1];
    for (int i = 0; i < n; ++i) {
        scanf("%d",&number[i]);
    }
    number[n+1]=-1;
    quicksort(number,n);
    int cnt=0;
    for (int i = 0; i < n; ++i) {
        cnt++;
        if (number[i]==number[i+1]) cnt--;
    }
    printf("%d\n",cnt);
    for (int i = 0; i < n; ++i) {
        if (number[i] != number[i + 1]) printf("%d ", number[i]);
    }
    return 0;
}

洛谷P1093 奖学金

结构体排序问题，挺有收获的，语法和算法方面。

先用快排排好结构体。注意写对swap函数

然后用冒泡排序的思想排出2,3条件即可

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <cstdlib>
#include <ctime>


struct stu {
    int index;
    int cn, mh, en;
    int sum;
} student[310];


// 为什么用位运算交换就会错？
void swap(stu *a, stu *b) {
    int t=a->sum;
    a->sum=b->sum;
    b->sum=t;

    t=a->cn;
    a->cn=b->cn;
    b->cn=t;

    t=a->index;
    a->index=b->index;
    b->index=t;
}

void quicksort(stu arr[], int len) {
    if (len <= 1) return;
    srand((unsigned) time(NULL));
    const int temp = arr[rand() % len ].sum;
    int i = 0, j = 0, k = len;
    while (i < k) {
        if (arr[i].sum > temp) {
            swap(&arr[i], &arr[j]);
            i++;
            j++;
        } else if (temp > arr[i].sum) {
            swap(&arr[i], &arr[k - 1]);
            k--;
        } else i++;
    }
    quicksort(arr, j);
    quicksort(arr + k, len - k);
}


int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        student[i].index = i + 1;
        scanf("%d %d %d", &student[i].cn, &student[i].mh, &student[i].en);
        student[i].sum = student[i].cn + student[i].en + student[i].mh;
    }
    quicksort(student, n);
    int in = 0;
    while (in == 0) {
        in = 1;
        for (int i = 0; i < n; ++i) {
            if (student[i].sum == student[i + 1].sum) {
                if (student[i].cn < student[i + 1].cn) {
                    swap(&student[i], &student[i + 1]);
                    in = 0;
                } else if (student[i].cn == student[i + 1].cn && student[i].index > student[i + 1].index) {
                    swap(&student[i], &student[i + 1]);
                    in = 0;
                }
            }
        }
    }
    for (int i = 0; i < 5; ++i) {
        printf("%d %d\n", student[i].index, student[i].sum);
    }

    return 0;
}

洛谷P1781 宇宙选举

本来以为非常简单，但是发现涉及大整数处理（如果用python这种就丝毫没有问题）

只要选出一个，所以找出max就可以了，应该不用排序

感觉指针这种东西挺奇妙，结构体配上数组直接整死我。

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 <cstdio>
#include <cstring>

struct per{
    int index;
    char vote[1000];
}person[25];

per max(per a,per b){
    if (strlen(a.vote)>strlen(b.vote))
        return a;
    else if (strlen(a.vote)<strlen(b.vote))
        return b;
    else {
        if (strcmp(a.vote, b.vote) > 0) {
            return a;
        } else return b;
    }
}

int main(){
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        person[i].index=i+1;
        scanf("%s",person[i].vote);
    }
    strcpy(person[24].vote,person[0].vote);
    person[24].index=person[0].index;
    for (int i = 0; i < n; ++i) {
        person[24].index=max(person[24],person[i]).index;
        strcpy(person[24].vote,max(person[24],person[i]).vote);
    }
    printf("%d\n",person[24].index);
    printf("%s",person[24].vote);
    return 0;
}

洛谷P1104 生日

可以用结构体做，用快排，之前写过一个了，不过这次想用c++的sort()试一下，就当自己练练c++的语法。

自己写一个cmp就可以了

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 <bits/stdc++.h>  //万能头文件

using namespace std; //没有这个底下的就都要std::

struct per {
    string s;
    int y, m, d, index;
} person[200];

bool cmp(per a, per b) {
    if (a.y < b.y)return 1;
    if (a.y > b.y)return 0;
    if (a.y == b.y) {
        if (a.m < b.m)return 1;
        if (a.m > b.m)return 0;
        if (a.m == b.m) {
            if (a.d < b.d)return 1;
            if (a.d > b.d)return 0;
            if (a.d == b.d) {
                if (a.index > b.index)return 1;
                else return 0;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> person[i].s >> person[i].y >> person[i].m >> person[i].d;
        person[i].index = i;
    }
    sort(person + 1, person + n + 1, cmp);
    for (int i = 1; i <= n; i++)cout << person[i].s << endl;
    return 0;
}

反思：

这种题可以用数学思维附上加权，然后排序就可以了，（通俗说就是加权加到一科考好就可以在其他科不考的情况下卷赢其他人）

貌似要多条件排序都可以这样做，比如

year*10000+mouth*100+day

如果部分条件是倒序就减掉就可以了:

score*10000+(10000-index)

洛谷P1116 车厢重组

冒泡排序，加个count就可以了，单纯想熟悉一下

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
#include <cstdio>

void swap(int*a,int*b){
    int t = *a;
    *a=*b;
    *b=t;
}

int cnt=0;

void bubble_sort(int arr[], int n) {
    int in = 1;
    while (in) {
        in = 0;
        for (int i = 0; i < n-1; ++i) {
            if (arr[i] > arr[i + 1]) {
                in = 1;
                cnt++;
                swap(&arr[i],&arr[i+1]);
            }
        }
    }
}

int main(){
    int n;
    scanf("%d",&n);
    int car[n+1];
    for (int i = 0; i < n; ++i) {
        scanf("%d",&car[i]);
    }
    bubble_sort(car,n);
    printf("%d",cnt);
    return 0;
}

洛谷P1068 分数线划定

又是结构体。。。那就用加权吧（

要注意weight[d-1]，用d就错了

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
#include <bits/stdc++.h>

int weight[5010];

void swap(int *a,int *b){
    int t=*a;
    *a=*b;
    *b=t;
}

void quicksort(int arr[],int len) {
    if (len <= 1) return;
    srand((unsigned)time(NULL));
    const int pivot = arr[rand() % len];
    int i = 0, j = 0, k = len;
    while (i < k) {
        if (arr[i] > pivot){
            swap(&arr[i], &arr[j]);
            i++;j++;}
        else if (pivot > arr[i]){
            swap(&arr[i], &arr[k-1]);
            k--;}
        else
            i++;
    }
    quicksort(arr, j);
    quicksort(arr + k, len - k);
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int a,b;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d",&a,&b);
        weight[i]=(b+1)*10000-a;
    }
    quicksort(weight,n);
    int d=(int)m*1.5;
    int score=weight[d-1]/10000;
    while (weight[d-1]/10000==score) {
        d++;
    }
    d--;
    printf("%d %d\n",weight[d-1]/10000,d);
    int i=0;
    while (weight[i]/10000>=score){
        printf("%d %d\n",10000-weight[i]%10000,weight[i]/10000);
        i++;
    }
}

洛谷P5143 攀爬者

又是结构体？感觉挺简单，却是个提高题

用加权，然后把距离加起来就可以了

后面的测试数据好大，用longlong

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
#include <bits/stdc++.h>

void swap(long long *a,long long *b){
    long long t=*a;
    *a=*b;
    *b=t;
}

void quick_sort(long long arr[],long long len) {
    if (len <= 1) return;
    srand((unsigned)time(NULL));
    const long long pivot = arr[rand() % len];
    long long i = 0, j = 0, k = len;
    while (i < k) {
        if (arr[i] < pivot){
            swap(&arr[i], &arr[j]);
            i++;j++;}
        else if (pivot < arr[i]){
            swap(&arr[i], &arr[k-1]);
            k--;}
        else
            i++;
    }
    quick_sort(arr, j);
    quick_sort(arr + k, len - k);
}

int main(){
    long long n;
    scanf("%lld",&n);
    long long location[n+1];
    long long x,y,z;
    for (long long i = 0; i < n; ++i) {
        scanf("%lld%lld%lld",&x,&y,&z);
        location[i]=z*100000000+y*10000+x;
    }
    quick_sort(location,n);
    long double sum=0;
    for (long long i = 0; i < n-1; ++i) {
        long long z1=location[i]/100000000;
        long long y1=(location[i]%100000000)/10000;
        long long x1=(location[i]%100000000)%10000;

        long long z2=location[i+1]/100000000;
        long long y2=(location[i+1]%100000000)/10000;
        long long x2=(location[i+1]%100000000)%10000;
        sum+=sqrt(1.0*((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+(z2-z1)*(z2-z1)));
    }
    printf("%.3Lf",sum);
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是： https://blog.ryaoknw.site/2020/12/a7d68e1b79ca/

更新于：2022年9月21日

排序

算法

评论