《算法笔记》4.1小节——算法初步->排序

问题A：排序

题目

题目描述

对输入的 n 个数进行排序并输出。

输入

输入的第一行包括一个整数 n (1<=n<=100)。 接下来的一行包括n个整数。

输出

可能有多组测试数据，对于每组数据，将排序后的 n 个整数输出，每个数后面都有一个空格。 每组测试数据的结果占一行。

样例输入

1
2
5
5 4 3 1 2

样例输出

1
1 2 3 4 5

题解

思路

思路很简单，num变量保存个数，一个n[100]数组保存数据，然后使用sort(n, n + num)排序即可。最后printf("%d ", n[i])输出。

代码

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
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
    int n[100], num = 0;
    while (scanf("%d", &num) != EOF)
    {
        for (int i = 0; i < num; i++)
        {
            scanf("%d", &n[i]);
        }
        sort(n, n + num);
        for (int i = 0; i < num; i++)
        {
            printf("%d ", n[i]);
        }
        printf("\n");
    }

    system("pause");
    return 0;
}

问题B：特殊排序

题目

题目描述

输入一系列整数，将其中最大的数挑出，并将剩下的数进行排序。

输入

输入第一行包括 1 个整数 N，1 <= N <= 1000，代表输入数据的个数。

接下来的一行有 N 个整数。

输出

可能有多组测试数据，对于每组数据，

第一行输出一个整数，代表 N 个整数中的最大值，并将此值从数组中去除，将剩下的数进行排序。

第二行将排序的结果输出。

样例输入

1
2
5
5 3 2 4 1

样例输出

1
2
5
1 2 3 4

提示

如果数组中只有一个数，当第一行将其输出后，第二行请输出"-1"。

题解

思路

跟上一题的思路基本一致，但是需要注意数组大小n[1000]，然后就是先输出最大值n[num - 1]即可。接着正常输出，到下标num - 2，需要判断的是如果只有一个数，那么第二行的输出为"-1"。

代码

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
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
    int n[1000], num = 0;
    while (scanf("%d", &num) != EOF)
    {
        for (int i = 0; i < num; i++)
        {
            scanf("%d", &n[i]);
        }
        sort(n, n + num);
        printf("%d\n", n[num - 1]);
        if (num == 1)
        {
            printf("-1\n");
        }
        else
        {
            for (int i = 0; i < num - 1; i++)
            {
                printf("%d ", n[i]);
            }
            printf("\n");
        }
    }

    system("pause");
    return 0;
}

问题C：EXCEL排序

题目

题目描述

Excel 可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。

对每个测试用例，首先输出 1 行 “Case i:”，其中 i 是测试用例的编号（从 1 开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2 时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。

输入

测试输入包含若干测试用例。每个测试用例的第 1 行包含两个整数 N (N<=100000) 和 C，其中 N 是纪录的条数，C 是指定排序的列号。以下有 N 行，每行包含一条学生纪录。每条学生纪录由学号（ 6 位数字，同组测试中没有重复的学号）、姓名（不超过 8 位且不包含空格的字符串）、成绩（闭区间 [0, 100] 内的整数）组成，每个项目间用1个空格隔开。当读到 N=0 时，全部输入结束，相应的结果不要输出。

输出

对每个测试用例，首先输出 1 行“Case i:”，其中 i 是测试用例的编号（从 1 开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2 时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4 1
000001 Zhao 75
000004 Qian 88
000003 Li 64
000002 Sun 90
4 2
000005 Zhao 95
000011 Zhao 75
000007 Qian 68
000006 Sun 85
4 3
000002 Qian 88
000015 Li 95
000012 Zhao 70
000009 Sun 95
0 3

样例输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Case 1:
000001 Zhao 75
000002 Sun 90
000003 Li 64
000004 Qian 88
Case 2:
000007 Qian 68
000006 Sun 85
000005 Zhao 95
000011 Zhao 75
Case 3:
000012 Zhao 70
000002 Qian 88
000009 Sun 95
000015 Li 95

题解

思路

需要创建结构体Record

1
2
3
4
5
6
7
struct Record
{
    long number;
    char name[10];
    int score;
    int c;
};

这里的c是方便比较用的，因为在bool cmp()函数里需要对c进行判断，而且每个case里的c都是不变的。对姓名进行非递减字典序排序时，需要用strcmp()函数。非递减序就是递增序，就是r2比r1大；所以strcmp(r1.name, r2.name) < 0时，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
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
78
79
80
81
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

struct Record
{
    long number;
    char name[10];
    int score;
    int c;
};

bool cmp(Record r1, Record r2)
{
    switch (r1.c)
    {
    case 1:
        return r1.number < r2.number;
        break;
    case 2:
        if (strcmp(r1.name, r2.name) != 0)
        {
            if (strcmp(r1.name, r2.name) < 0)
            {
                return 1;
            }
            else
            {
                return 0;
            };
        }
        else
        {
            return r1.number < r2.number;
        }
        break;
    case 3:
        if (r1.score != r2.score)
        {
            return r1.score < r2.score;
        }
        else
        {
            return r1.number < r2.number;
        }
    default:
        break;
    }
}

int main()
{
    int N = 0, C = 0, cases = 1;
    while (scanf("%d %d", &N, &C) != EOF)
    {
        if (N == 0)
        {
            break;
        }

        Record *record = new Record[N];
        for (int i = 0; i < N; i++)
        {
            record[i].c = C;
            scanf("%d %s %d", &record[i].number, &record[i].name, &record[i].score);
        }
        sort(record, record + N, cmp);
        printf("Case %d:\n", cases++);
        for (int i = 0; i < N; i++)
        {
            printf("%06d %s %d\n", record[i].number, record[i].name, record[i].score);
        }
    }

    system("pause");
    return 0;
}

问题D：字符串内排序

题目

题目描述

输入一个字符串，长度小于等于 200，然后将输出按字符顺序升序排序后的字符串。

输入

测试数据有多组，输入字符串。

输出

对于每组输入,输出处理后的结果。

样例输入

1
tianqin

样例输出

1
aiinnqt

提示

注意输入的字符串中可能有空格。

题解

思路

这里提到字符串长度小于等于 200，这里的字符串长度最好大于 200，比如 210、205 等，当然 201 也是可以的。因为有空格所以要用cin.getline(s, 201)，这里的 201 是因为要多一个，null 终结符。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
   char s[210] = "";
   while (cin.getline(s, 201))
   {
       int len = strlen(s);
       sort(s, s + len);
       printf("%s\n", s);
       strcpy(s, "");
   }

   system("pause");
   return 0;
}

问题E：Problem B

题目

题目描述

请写一个程序，对于一个 m 行 m 列的（1<m<10）的方阵，求其每一行，每一列及主对角线元素之和，最后按照从大到小的顺序依次输出。

输入

共一组数据，输入的第一行为一个正整数，表示 m，接下来的 m 行，每行 m 个整数表示方阵元素。

输出

从大到小排列的一行整数，每个整数后跟一个空格，最后换行。

样例输入

1
2
3
4
5
4
15 8 -2 6
31 24 18 71
-3 -9 27 13
17 21 38 69

样例输出

1
159 145 144 135 81 60 44 32 28 27

题解

思路

需要计算行和与列和还有主次对角线和，最后还要记得换行。

代码

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
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

bool cmp(int a, int b)
{
    return a > b;
}

int main()
{
    int m = 0;
    while (scanf("%d", &m) != EOF)
    {
        int num[10][10] = {0}, res[22] = {0}, index = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < m; j++)
            {
                scanf("%d", &num[i][j]);
            }
        }
        // 求行和
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < m; j++)
            {
                res[index] += num[i][j];
            }
            index++;
        }
        // 求列和
        for (int j = 0; j < m; j++)
        {
            for (int i = 0; i < m; i++)
            {
                res[index] += num[i][j];
            }
            index++;
        }
        // 求对角线
        for (int i = 0; i < m; i++)
        {
            res[index] += num[i][i];
            res[index + 1] += num[i][m - i - 1];
        }
        index += 2;
        sort(res, res + index, cmp);
        for (int i = 0; i < index; i++)
        {
            i == 0 ? printf("%d", res[i]) : printf(" %d", res[i]);
        }
        printf("\n");
    }

    system("pause");
    return 0;
}

问题 F: 小白鼠排队

题目

题目描述

N 只小白鼠(1 <= N <= 100)，每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量，要求按照白鼠重量从大到小的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”，“blue” 等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。

输入

多案例输入，每个案例的输入第一行为一个整数 N，表示小白鼠的数目。

下面有 N 行，每行是一只白鼠的信息。第一个为不大于 100 的正整数，表示白鼠的重量；第二个为字符串，表示白鼠的帽子颜色，字符串长度不超过 10 个字符。

注意：白鼠的重量各不相同。

输出

每个案例按照白鼠的重量从大到小的顺序输出白鼠的帽子颜色。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
1
79 omi
9
46 lcg
92 cru
37 ceq
54 vhr
17 wus
27 tnv
13 kyr
95 wld
34 qox

样例输出

1
2
3
4
5
6
7
8
9
10
omi
wld
cru
vhr
lcg
ceq
qox
tnv
wus
kyr

题解

思路

思路很简单，首先创建一个结构体mouse，属性为重量weight与帽子颜色hat，然后对结构体排序即可，需要重写cmp方法根据weight排序。

代码

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 <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

struct mouse
{
    int weight;
    char hat[11];
};

bool cmp(mouse m1, mouse m2)
{
    return m1.weight > m2.weight;
}

int main()
{
   int n = 0;
   while (scanf("%d", &n) != EOF)
   {
       mouse mice[100];
       for (int i = 0; i < n; i++)
       {
           scanf("%d %s", &mice[i].weight, mice[i].hat);
       }
       sort(mice, mice + n, cmp);
       for (int i = 0; i < n; i++)
       {
           cout << mice[i].hat << endl;
       }
       
   }

   system("pause");
   return 0;
}

问题 G: 中位数

题目

题目描述

中位数定义：一组数据按从小到大的顺序依次排列，处在中间位置的一个数（或最中间两个数据的平均数）. 给出一组无序整数，求出中位数，如果求最中间两个数的平均数，向下取整即可（不需要使用浮点数）

输入

该程序包含多组测试数据，每一组测试数据的第一行为N，代表该组测试数据包含的数据个数，1<=N<=10000. 接着N行为N个数据的输入，N=0时结束输入

输出

输出中位数，每一组测试数据输出一行

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
468
15
501
170
725
479
359
963
465
706
146
282
828
962
492
996
943
0

样例输出

1
2
468
501

提示

按题目要求模拟即可

题解

思路

根据中位数的思路求即可。需要注意N为奇数时，num[count / 2]恰好为奇数。

代码

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 <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
    int count = 0, num[10000];
    while (scanf("%d", &count) != EOF)
    {
        if (count == 0)
        {
            break;
        }
        for (int i = 0; i < count; i++)
        {
            scanf("%d", &num[i]);
        }
        sort(num, num + count);
        if (count % 2 == 0)
        {
            printf("%d\n", (num[count / 2 - 1] + num[count / 2]) / 2);
        }
        else
        {
            printf("%d\n", num[count / 2]);
        }
    }

    system("pause");
    return 0;
}

问题 H: 整数奇偶排序

题目

题目描述

输入 10 个整数，彼此以空格分隔。重新排序以后输出(也按空格分隔)，要求： 1.先输出其中的奇数,并按从大到小排列； 2.然后输出其中的偶数,并按从小到大排列。

输入

任意排序的10个整数（0～100），彼此以空格分隔。

输出

可能有多组测试数据，对于每组数据，按照要求排序后输出，由空格分隔。

样例输入

1
2
0 56 19 81 59 48 35 90 83 75 
17 86 71 51 30 1 9 36 14 16

样例输出

1
2
83 81 75 59 35 19 0 48 56 90
71 51 17 9 1 14 16 30 36 86

提示

多组数据，注意输出格式

  1. 测试数据可能有很多组，请使用while(cin>>a[0]>>a[1]>>...>>a[9])类似的做法来实现;
  2. 输入数据随机，有可能相等。

题解

思路

这题我的思路是输入完十个数据之后，再新建两个数组，一个为奇数组，一个为偶数组，依次赋值，分别排序，再统一分别输出。这个时候需要注意：可能全为奇数或者全为偶数，因此各自输出时要控制好输出格式，避免多输出或少输出空格。

代码

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
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

bool cmp(int a, int b)
{
    return a > b;
}

int main()
{
    int num[10], a[10], b[10];
    while (cin >> num[0] >> num[1] >> num[2] >> num[3] >> num[4] >> num[5] >> num[6] >> num[7] >> num[8] >> num[9])
    {
        int k = 0, j = 0;
        for (int i = 0; i < 10; i++)
        {
            if (num[i] % 2 == 0)
            {
                a[k++] = num[i];
            }
            else
            {
                b[j++] = num[i];
            }
        }
        sort(a, a + k);
        sort(b, b + j, cmp);
        for (int i = 0; i < j; i++)
        {
            i == 0 ? printf("%d", b[i]) : printf(" %d", b[i]);
        }
        if (k != 0)
        {
            printf(" ");
        }
        for (int i = 0; i < k; i++)
        {
            i == 0 ? printf("%d", a[i]) : printf(" %d", a[i]);
        }
        printf("\n");
    }

    system("pause");
    return 0;
}

问题 I: 排名

题目

题目描述

今天的上机考试虽然有实时的Ranklist，但上面的排名只是根据完成的题数排序，没有考虑每题的分值，所以并不是最后的排名。给定录取分数线，请你写程序找出最后通过分数线的考生，并将他们的成绩按降序打印。

输入

测试输入包含若干场考试的信息。每场考试信息的第1行给出考生人数N ( 0 < N < 1000 )、考题数M ( 0 < M < = 10 )、分数线（正整数）G；第2行排序给出第1题至第M题的正整数分值；以下N行，每行给出一名考生的准考证号（长度不超过20的字符串）、该生解决的题目总数m、以及这m道题的题号（题目号由1到M）。 当读入的考生人数为0时，输入结束，该场考试不予处理。

输出

对每场考试，首先在第1行输出不低于分数线的考生人数n，随后n行按分数从高到低输出上线考生的考号与分数，其间用1空格分隔。若有多名考生分数相同，则按他们考号的升序输出。

样例输入

1
2
3
4
5
6
3 5 32
17 10 12 9 15
CS22003 5 1 2 3 4 5
CS22004 3 5 1 3
CS22002 2 1 5
0

样例输出

1
2
3
4
3
CS22003 63
CS22004 44
CS22002 32

提示

这题比较简单，计算好每个人的分数后按题目要求排序即可。

题解

思路

题目比较长，但是不难，结构体排序，需要注意计算分数时要对应好下标关系。

代码

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
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

struct exer
{
    char id[21];
    int solve;
    int score;
};

bool cmp(exer ex1, exer ex2)
{
    return ex1.score > ex2.score;
}

int main()
{
    int N = 0, M = 0, G = 0, qes[10];
    exer ex[1000];
    while (scanf("%d", &N) != EOF)
    {
        if (N == 0)
        {
            break;
        }
        scanf("%d %d", &M, &G);
        for (int i = 0; i < M; i++)
        {
            scanf("%d", &qes[i]);
        }
        int exNum = 0;
        for (int i = 0; i < N; i++)
        {
            scanf("%s %d", ex[i].id, &ex[i].solve);
            for (int j = 0; j < ex[i].solve; j++)
            {
                int index;
                scanf("%d", &index);
                // 此处注意是 index - 1
                ex[i].score += qes[index - 1];
            }
            if (ex[i].score >= G)
            {
                exNum++;
            }
        }
        sort(ex, ex + N, cmp);
        printf("%d\n", exNum);
        for (int i = 0; i < exNum; i++)
        {
            printf("%s %d\n", ex[i].id, ex[i].score);
        }
    }

    system("pause");
    return 0;
}
#算法 #算法笔记
《算法笔记》4.1小节——算法初步->排序
https://excelius.xyz/《算法笔记》4-1小节——算法初步-排序/
作者
Excelius
发布于
2022年1月29日
许可协议