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

问题A：排序

题目

题目描述

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

输入

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

输出

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

样例输入

5
5 4 3 1 2

样例输出

1 2 3 4 5 

题解

思路

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

代码

#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 个整数中的最大值，并将此值从数组中去除，将剩下的数进行排序。

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

样例输入

5
5 3 2 4 1

样例输出

5
1 2 3 4

提示

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

题解

思路

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

代码

#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 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。

样例输入

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

样例输出

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

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的结果为真。

代码

#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，然后将输出按字符顺序升序排序后的字符串。

输入

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

输出

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

样例输入

tianqin

样例输出

aiinnqt

提示

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

题解

思路

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

代码

#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 个整数表示方阵元素。

输出

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

样例输入

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

样例输出

159 145 144 135 81 60 44 32 28 27

题解

思路

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

代码

#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
79 omi
9
46 lcg
92 cru
37 ceq
54 vhr
17 wus
27 tnv
13 kyr
95 wld
34 qox

样例输出

omi
wld
cru
vhr
lcg
ceq
qox
tnv
wus
kyr

题解

思路

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

代码

#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
468
15
501
170
725
479
359
963
465
706
146
282
828
962
492
996
943
0

样例输出

468
501

提示

按题目要求模拟即可

题解

思路

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

代码

#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），彼此以空格分隔。

输出

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

样例输入

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

样例输出

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. 输入数据随机，有可能相等。

题解

思路

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

代码

#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空格分隔。若有多名考生分数相同，则按他们考号的升序输出。

样例输入

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

样例输出

3
CS22003 63
CS22004 44
CS22002 32

提示

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

题解

思路

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

代码

#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;
}