跳转至

J-L23 排序

覆盖词条：KJ-34a~e ｜ 先修：J-L09/L15

排序概念 · 手写排序

冒泡排序过程1

冒泡排序过程

题目描述

输入 \(n\) 个整数，用冒泡排序将它们从小到大排列。要求输出每一轮结束后的数组状态（共 \(n-1\) 轮，每行一个状态，数间用空格分隔）。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个整数。

输出格式

共 \(n-1\) 行，为每轮结束后的数组状态。

样例输入

1
2
4
5 2 4 1

样例输出

1
2
3
2 4 1 5
2 1 4 5
1 2 4 5

数据范围

  • \(1 \le n \le 100\)，整数绝对值 \(\le 10^9\)

⬇ 点击下载数据包

冒泡排序过程 AC 代码

解题思路

冒泡排序每轮从左到右依次比较相邻两个数，逆序就交换——每一轮把当前最大值「沉」到末尾。写完双重循环后，每轮结束把整个数组输出一遍即可。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    for (int i = 0; i + 1 < n; i++) {          // 共 n-1 轮
        for (int j = 0; j + 1 < n - i; j++)    // 相邻比较，大数沉底
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
        for (int j = 0; j < n; j++) cout << a[j] << " \n"[j == n - 1];
    }
    return 0;
}

选择排序过程2

选择排序过程

题目描述

输入 \(n\) 个整数，用选择排序将它们从小到大排列：每一轮从未排序部分选出最小值，与未排序部分的开头交换。输出每一轮结束后的数组状态（共 \(n-1\) 轮）。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个整数。

输出格式

共 \(n-1\) 行，为每轮结束后的数组状态。

样例输入

1
2
4
5 2 4 1

样例输出

1
2
3
1 2 4 5
1 2 4 5
1 2 4 5

数据范围

  • \(1 \le n \le 100\)，整数绝对值 \(\le 10^9\)

⬇ 点击下载数据包

选择排序过程 AC 代码

解题思路

每轮扫描未排序区间记录最小值下标，结束后与区间开头交换并输出——注意先找完再交换，不能边扫边换。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    for (int i = 0; i + 1 < n; i++) {          // 共 n-1 轮，为位置 i 选最小值
        int mi = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[mi]) mi = j;
        swap(a[i], a[mi]);
        for (int j = 0; j < n; j++) cout << a[j] << " \n"[j == n - 1];
    }
    return 0;
}

插入排序过程3

插入排序过程

题目描述

输入 \(n\) 个整数，用插入排序将它们从小到大排列：依次把第 \(2 \sim n\) 个数插入到前面已排序部分的正确位置。输出每次插入完成后的数组状态（共 \(n-1\) 行）。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个整数。

输出格式

共 \(n-1\) 行，为每次插入后的数组状态。

样例输入

1
2
4
5 2 4 1

样例输出

1
2
3
2 5 4 1
2 4 5 1
1 2 4 5

数据范围

  • \(1 \le n \le 100\)，整数绝对值 \(\le 10^9\)

⬇ 点击下载数据包

插入排序过程 AC 代码

解题思路

保存待插入值 \(v\)，从后往前把比 \(v\) 大的数逐个后挪，找到位置后放入 \(v\)；每次插入完成输出整个数组。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    for (int i = 1; i < n; i++) {              // 把 a[i] 插入前面已有序的部分
        long long v = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > v) {
            a[j + 1] = a[j];                   // 比它大的往后挪
            j--;
        }
        a[j + 1] = v;
        for (int k = 0; k < n; k++) cout << a[k] << " \n"[k == n - 1];
    }
    return 0;
}

分数分布统计4

分数分布统计

题目描述

输入 \(n\) 个 0 到 100 之间的整数（分数），统计每个出现过的分数各有多少人，按分数从小到大输出（每行「分数 人数」）。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个整数。

输出格式

若干行，每行两个整数：分数与该分数的人数（只输出出现过的分数）。

样例输入

1
2
6
90 85 90 60 85 100

样例输出

1
2
3
4
60 1
85 2
90 2
100 1

数据范围

  • \(1 \le n \le 1000\)，分数为 0 ~ 100 的整数

⬇ 点击下载数据包

分数分布统计 AC 代码

解题思路

计数排序思想：开一个 101 的计数数组，读到分数 \(x\) 就 cnt[x]++；最后从小到大扫一遍，非零的输出——计数数组本身就是排好序的。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> cnt(101, 0);                   // 计数数组：cnt[x] = 分数 x 的人数
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    for (int x = 0; x <= 100; x++)
        if (cnt[x]) cout << x << " " << cnt[x] << "\n";
    return 0;
}

三个数排序5

三个数排序

题目描述

输入三个整数，从小到大输出。

输入格式

一行三个整数。

输出格式

一行三个整数，用空格分隔。

样例输入

1
3 1 2

样例输出

1
1 2 3

数据范围

  • 整数绝对值 \(\le 10^9\)

⬇ 点击下载数据包

三个数排序 AC 代码

解题思路

三次两两比较交换：先保证 \(a \le b\)，再保证 \(a \le c\)，最后保证 \(b \le c\)——最小入门排序。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b, c;
    cin >> a >> b >> c;
    if (a > b) swap(a, b);
    if (a > c) swap(a, c);
    if (b > c) swap(b, c);                     // 三次两两比较后必为升序
    cout << a << " " << b << " " << c << "\n";
    return 0;
}

车厢重组6

车厢重组

题目描述

\(n\) 节车厢按某种顺序进站，每次只能交换相邻两节车厢。求最少交换多少次才能把车厢按编号从小到大排好。

输入格式

第一行一个整数 \(N\)；第二行 \(N\) 个互不相同的数，表示初始车厢顺序（数据可能分行输入）。

输出格式

一个整数，为最少的交换次数。

样例输入

1
2
4
4 3 2 1

样例输出

1
6

数据范围

  • \(N \le 1000\)
车厢重组 AC 代码

解题思路

相邻交换排序的最少次数就是冒泡排序的交换次数：双重循环模拟冒泡，统计交换次数即可（它等于逆序对数，\(n\) 小时 \(O(n^2)\) 足够）。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    long long cnt = 0;
    // 冒泡排序：数相邻交换次数（即逆序对数，n ≤ 10000 可 O(n^2)）
    for (int i = 0; i + 1 < n; i++)
        for (int j = 0; j + 1 < n - i; j++)
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                cnt++;
            }
    cout << cnt << "\n";
    return 0;
}

选举学生会7

选举学生会

题目描述

学生会选举共收到 \(m\) 张选票，每张选票写了一个候选人编号（\(1 \sim n\)）。把这些选票按编号从小到大排序输出（\(m\) 可达 \(2 \times 10^6\)，请使用高效的排序方法）。

输入格式

第一行两个整数 \(n, m\)；第二行 \(m\) 个整数，为选票上的编号。

输出格式

一行，排序后的选票编号，用空格分隔。

样例输入

1
2
3 5
3 1 2 1 3

样例输出

1
1 1 2 3 3

数据范围

  • \(1 \le n \le 999\)，\(1 \le m \le 2 \times 10^6\)
选举学生会 AC 代码

解题思路

计数排序：编号范围只有 \(1 \sim n\)，开计数数组统计每个编号的票数，再从小到大按次数展开输出——\(O(n + m)\)，比任何基于比较的排序都快。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> cnt(n + 1, 0);                 // 计数排序：票数 m 高达 2e6
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    for (int x = 1; x <= n; x++)
        for (int k = 0; k < cnt[x]; k++) cout << x << " ";
    return 0;
}

明明的随机数8

明明的随机数

题目描述

生成了 \(N\) 个 \(1 \sim 1000\) 之间的随机整数，对重复的数字只保留一个，再把不同的数从小到大排序输出：第一行输出不同数的个数 \(M\)，第二行输出排序后的 \(M\) 个数。

输入格式

第一行一个正整数 \(N\)；第二行 \(N\) 个正整数。

输出格式

两行：第一行为不同随机数的个数；第二行为排序后的不同随机数。

样例输入

1
2
10
20 40 32 67 40 20 89 300 400 15

样例输出

1
2
8
15 20 32 40 67 89 300 400

数据范围

  • \(1 \le N \le 100\)，随机数为 \(1 \sim 1000\) 的整数
明明的随机数 AC 代码

解题思路

值域只有 1000——用布尔桶标记出现过的数（天然去重），从小到大扫描输出即可（NOIP2006 T1）。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> bucket(1001, 0);               // 值域 1~1000 的桶
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        bucket[x] = 1;                         // 标记出现（天然去重）
    }
    int m = 0;
    for (int x = 1; x <= 1000; x++)
        if (bucket[x]) m++;
    cout << m << "\n";
    for (int x = 1; x <= 1000; x++)
        if (bucket[x]) cout << x << " ";
    return 0;
}

【模板】排序9

【模板】排序

题目描述

将读入的 \(N\) 个数从小到大排序后输出（\(N\) 可达 \(10^5\)，请使用高效的排序方法）。

输入格式

第一行一个正整数 \(N\)；第二行 \(N\) 个正整数。

输出格式

一行，排序后的 \(N\) 个数，用空格分隔。

样例输入

1
2
5
4 2 4 5 1

样例输出

1
1 2 4 4 5

数据范围

  • \(1 \le N \le 10^5\)，\(1 \le a_i \le 10^9\)
【模板】排序 AC 代码

解题思路

直接使用 STL 的 sort()——它是 \(O(n \log n)\) 的高效排序，手写冒泡在 \(N = 10^5\) 下必然超时。比较器默认升序。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
    return 0;
}

sort() 与结构体排序

成绩单10

成绩单

题目描述

输入 \(n\) 个学生的姓名和成绩，按成绩从高到低输出姓名；成绩相同的保持输入的先后顺序（稳定）。

输入格式

第一行一个整数 \(n\)；接下来 \(n\) 行，每行为姓名（无空格）和成绩。

输出格式

\(n\) 行，每行一个姓名。

样例输入

1
2
3
4
3
Alice 90
Bob 90
Carol 85

样例输出

1
2
3
Alice
Bob
Carol

数据范围

  • \(1 \le n \le 1000\)，姓名长度不超过 20，成绩为 0 ~ 100 的整数

⬇ 点击下载数据包

成绩单 AC 代码

解题思路

结构体排序 + 稳定性：sort 本身不稳定，比较器里加一条「同分比输入下标」就能手动保证稳定——下标小的排前面。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

struct Stu {
    string name;
    int score, idx;
};

int main() {
    int n;
    cin >> n;
    vector<Stu> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].name >> v[i].score;
        v[i].idx = i;
    }
    // 分数降序；同分保持输入先后（比较下标，保证稳定）
    sort(v.begin(), v.end(), [](const Stu& x, const Stu& y) {
        if (x.score != y.score) return x.score > y.score;
        return x.idx < y.idx;
    });
    for (auto& s : v) cout << s.name << "\n";
    return 0;
}

单词排序11

单词排序

题目描述

输入 \(n\) 个英文单词（小写字母），按字典序从小到大输出。

输入格式

第一行一个整数 \(n\)；接下来 \(n\) 行，每行一个单词。

输出格式

\(n\) 行，为排序后的单词。

样例输入

1
2
3
4
5
4
banana
apple
cherry
apple

样例输出

1
2
3
4
apple
apple
banana
cherry

数据范围

  • \(1 \le n \le 1000\)，单词长度 \(\le 20\)

⬇ 点击下载数据包

单词排序 AC 代码

解题思路

string 自带字典序比较（先比首字符，相同再比第二个……），直接 sort 即可。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> w(n);
    for (auto& s : w) cin >> s;
    sort(w.begin(), w.end());                  // string 自带字典序比较
    for (auto& s : w) cout << s << "\n";
    return 0;
}

奇偶重排12

奇偶重排

题目描述

输入 \(n\) 个互不相同的整数，重排为：所有奇数在前（升序），所有偶数在后（降序）。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个整数。

输出格式

一行 \(n\) 个整数，用空格分隔。

样例输入

1
2
6
5 2 8 3 6 1

样例输出

1
1 3 5 8 6 2

数据范围

  • \(1 \le n \le 1000\)，整数绝对值 \(\le 10^9\)

⬇ 点击下载数据包

奇偶重排 AC 代码

解题思路

自定义比较器：两个数奇偶性不同时奇数排前面；同为奇数比大小（升序）；同为偶数比大小（降序）——一个比较器表达全部规则。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    // 奇数在前升序，偶数在后降序
    sort(a.begin(), a.end(), [](long long x, long long y) {
        bool ox = x % 2, oy = y % 2;
        if (ox != oy) return ox > oy;          // 奇数优先
        return ox ? x < y : x > y;             // 奇升偶降
    });
    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
    return 0;
}

最厉害的学生13

最厉害的学生

题目描述

输入 \(n\) 个学生的姓名和语文、数学、英语三科成绩，输出总分最高的学生的姓名；总分相同的输出最先出现在输入中的那位。

输入格式

第一行一个整数 \(n\)；接下来 \(n\) 行，每行为姓名与三个整数。

输出格式

一行，为总分最高学生的姓名。

样例输入

1
2
3
4
3
Alice 90 90 90
Bob 100 80 90
Carol 90 95 90

样例输出

1
Carol

数据范围

  • \(1 \le n \le 1000\)，姓名长度 \(\le 20\)，成绩为 0 ~ 150 的整数
最厉害的学生 AC 代码

解题思路

不必排序——边读边比：维护当前最高总分与对应姓名，严格大于才更新（并列自然保留先出现者）。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    string bestName;
    int best = -1;
    for (int i = 0; i < n; i++) {
        string name;
        int c, m, e;
        cin >> name >> c >> m >> e;
        int total = c + m + e;
        if (total > best) {                    // 并列取先出现者
            best = total;
            bestName = name;
        }
    }
    cout << bestName << "\n";
    return 0;
}

生日14

生日

题目描述

输入 \(n\) 个同学的姓名与出生日期（年、月、日），按年龄从大到小输出姓名（即出生日期早的在前）；生日完全相同的，输入靠后的同学先输出。

输入格式

第一行一个整数 \(n\)；接下来 \(n\) 行，每行为姓名、年、月、日。

输出格式

\(n\) 行，每行一个姓名。

样例输入

1
2
3
4
3
Yangchu 1992 4 23
Qiujingya 1993 10 13
Luowen 1991 8 1

样例输出

1
2
3
Luowen
Yangchu
Qiujingya

数据范围

  • \(1 \le n \le 100\)，姓名长度 \(\le 20\)
生日 AC 代码

解题思路

多关键字排序：年 → 月 → 日依次升序（出生早 = 年龄大）；同生日时输入下标大的优先——经典的多关键字 + 定制稳定性练习。

AC代码

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

struct Stu {
    string name;
    int y, m, d, idx;
};

int main() {
    int n;
    cin >> n;
    vector<Stu> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].name >> v[i].y >> v[i].m >> v[i].d;
        v[i].idx = i;
    }
    // 年龄从大到小 = 出生日期从早到晚；同生日后输入先输出
    sort(v.begin(), v.end(), [](const Stu& x, const Stu& y) {
        if (x.y != y.y) return x.y < y.y;
        if (x.m != y.m) return x.m < y.m;
        if (x.d != y.d) return x.d < y.d;
        return x.idx > y.idx;
    });
    for (auto& s : v) cout << s.name << "\n";
    return 0;
}

奖学金15

奖学金

题目描述

\(n\) 个学生各有语文、数学、英语三科成绩（每科 0~150）。先按总分从高到低排序；总分相同的按语文成绩从高到低；总分和语文都相同的按学号从小到大。输出前 5 名学生的学号和总分。

输入格式

第一行一个整数 \(n\)；接下来 \(n\) 行，每行三个整数，为该生三科成绩（学号按输入顺序为 \(1 \sim n\)）。

输出格式

共 5 行，每行两个整数：学号与总分。

样例输入

1
2
3
4
5
6
7
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

样例输出

1
2
3
4
5
6 265
4 264
3 258
2 244
1 237

数据范围

  • \(5 \le n \le 300\)，每科成绩 0 ~ 150
奖学金 AC 代码

解题思路

三关键字排序：比较器依次比总分、语文、学号——写好这一个函数，sort 一次完成（NOIP2007 T1）。

AC代码

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

struct Stu {
    int chinese, id, total;
};

int main() {
    int n;
    cin >> n;
    vector<Stu> v(n);
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[i] = {a, i + 1, a + b + c};
    }
    // 总分降序 → 语文降序 → 学号升序
    sort(v.begin(), v.end(), [](const Stu& x, const Stu& y) {
        if (x.total != y.total) return x.total > y.total;
        if (x.chinese != y.chinese) return x.chinese > y.chinese;
        return x.id < y.id;
    });
    for (int i = 0; i < 5; i++)
        cout << v[i].id << " " << v[i].total << "\n";
    return 0;
}

分数线划定16

分数线划定

题目描述

世博会志愿者选拔：共 \(n\) 人报名，计划录取 \(m\) 人。面试分数线为排名第 \(\lfloor m \times 150\% \rfloor\) 名的选手的分数；所有笔试成绩不低于分数线的选手进入面试。输出分数线与实际录取人数，再按成绩从高到低（同分按报名号从小到大）输出所有进入面试的选手。

输入格式

第一行两个整数 \(n, m\)；接下来 \(n\) 行，每行两个整数：报名号与笔试成绩。

输出格式

第一行两个整数：分数线与实际录取人数；接下来若干行为进入面试的选手（报名号 成绩）。

样例输入

1
2
3
4
5
6
7
6 3
1000 90
3239 88
2390 95
7231 84
1005 95
851 90

样例输出

1
2
3
4
5
6
88 5
1005 95
2390 95
851 90
1000 90
3239 88

（分数线 = 第 \(\lfloor 3 \times 150\% \rfloor = 4\) 名的分数 88；88 有重分，故 5 人进入面试。）

数据范围

  • \(5 \le n \le 5000\)，\(3 \le m \le n\)；报名号 \(1000 \sim 9999\)，成绩 \(1 \sim 100\)
分数线划定 AC 代码

解题思路

按「成绩降序、同分报名号升序」排序，分数线取第 \(\lfloor m \times 150\% \rfloor\) 位的成绩；再从前往后数出所有不低于分数线的选手输出（NOIP2009 T2）。

AC代码

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

struct P {
    int id, score, idx;
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<P> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].id >> v[i].score;
        v[i].idx = i;
    }
    // 分数降序 → 报名号升序
    sort(v.begin(), v.end(), [](const P& x, const P& y) {
        if (x.score != y.score) return x.score > y.score;
        return x.id < y.id;
    });
    int line = v[m * 150 / 100].score;         // 分数线 = 第 floor(m*150%) 名的分数
    int cnt = 0;
    for (auto& p : v) {
        if (p.score < line) break;             // 不低于分数线的全部录取
        cnt++;
    }
    cout << line << " " << cnt << "\n";
    for (int i = 0; i < cnt; i++)
        cout << v[i].id << " " << v[i].score << "\n";
    return 0;
}

小鱼比可爱17

小鱼比可爱

题目描述

\(n\) 条鱼从左到右排成一排，每条鱼有一个可爱程度。每条鱼只能看见它左边的鱼，请对每条鱼输出：在它左边的鱼中，有多少条不如它可爱。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个非负整数，为从左到右每条鱼的可爱程度。

输出格式

一行 \(n\) 个整数，用空格分隔。

样例输入

1
2
5
3 2 3 1 2

样例输出

1
0 0 1 0 1

数据范围

  • \(1 \le n \le 100\)，可爱程度为 0 ~ 10 的整数
小鱼比可爱 AC 代码

解题思路

对每条鱼扫描它左边的所有鱼，统计严格小于它的个数——\(n \le 100\) 时 \(O(n^2)\) 足够，本质是「排名计数」的朴素版。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < i; j++)            // 只看左边的鱼
            if (a[j] < a[i]) cnt++;            // 严格不如自己可爱
        cout << cnt << " \n"[i == n - 1];
    }
    return 0;
}

排序应用 · 统计与判定

欢乐的跳18

欢乐的跳

题目描述

一个 \(n\) 元素数组，如果相邻两元素之差的绝对值恰好包含 \(1 \sim n-1\) 之间的所有整数，则称其「欢乐的跳」（如 {1, 4, 2, 3} 的差为 3, 2, 1）。给定数组，判断它是否符合。

输入格式

第一行一个整数 \(n\)；接下来 \(n\) 个整数。

输出格式

符合输出 Jolly，否则输出 Not jolly。

样例输入

1
2
4
1 4 2 3

样例输出

1
Jolly

数据范围

  • \(1 \le n \le 1000\)，元素绝对值 \(\le 10^8\)
欢乐的跳 AC 代码

解题思路

计算所有相邻差的绝对值，排序后检查是否恰好为 \(1, 2, \ldots, n-1\)——排序把「集合是否完整」变成「依次比较」。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    vector<long long> diff;
    for (int i = 1; i < n; i++)
        diff.push_back(abs(a[i] - a[i - 1]));
    sort(diff.begin(), diff.end());
    for (int i = 0; i < (int)diff.size(); i++) {
        if (diff[i] != i + 1) {                // 相邻差应恰好为 1, 2, ..., n-1
            cout << "Not jolly\n";
            return 0;
        }
    }
    cout << "Jolly\n";
    return 0;
}

统计数字19

统计数字

题目描述

得到 \(n\) 个自然数（每个不超过 \(1.5 \times 10^9\)），统计每个数出现的次数，并按自然数从小到大的顺序输出统计结果。

输入格式

第一行一个整数 \(n\)；接下来 \(n\) 行，每行一个自然数。

输出格式

若干行，每行两个整数：自然数与出现次数（按自然数升序）。

样例输入

1
2
8
2 4 2 4 2 4 4 4

样例输出

1
2
2 3
4 5

数据范围

  • \(1 \le n \le 2 \times 10^5\)，数不超过 \(1.5 \times 10^9\)（值域太大不能开计数数组）
统计数字 AC 代码

解题思路

值域高达 \(1.5 \times 10^9\)，不能开桶——排序后同值必连续，从左到右扫一遍逐段统计即可（NOIP2007 T1）。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());
    int i = 0;
    while (i < n) {                            // 排序后同值必连续，逐段统计
        int j = i;
        while (j < n && a[j] == a[i]) j++;
        cout << a[i] << " " << j - i << "\n";
        i = j;
    }
    return 0;
}

第 k 小整数20

第 k 小整数

题目描述

现有 \(n\) 个正整数，求其中第 \(k\) 小的整数（相同大小的整数只计算一次）；若不存在输出 NO RESULT。

输入格式

第一行两个整数 \(n, k\)；第二行 \(n\) 个正整数。

输出格式

一个整数或 NO RESULT。

样例输入

1
2
10 5
1 3 3 7 2 5 1 2 9 7

样例输出

1
7

（去重后为 1、2、3、5、7、9，第 5 小是 7。）

数据范围

  • \(n \le 10000\)，\(k \le 4000\)，正整数小于 30000
第 k 小整数 AC 代码

解题思路

排序 → unique 去重 → 第 \(k\) 个就是答案；去重后不足 \(k\) 个输出 NO RESULT。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());   // 去重
    if (k > (int)a.size()) cout << "NO RESULT\n";
    else cout << a[k - 1] << "\n";
    return 0;
}

第 k 大21

第 k 大

题目描述

输入 \(n\) 个正整数，求其中第 \(k\) 大的整数（相同大小的整数只计算一次）；若不存在输出 NO RESULT。

输入格式

第一行两个整数 \(n, k\)；第二行 \(n\) 个正整数。

输出格式

一个整数或 NO RESULT。

样例输入

1
2
6 2
9 3 9 1 5 5

样例输出

1
5

（去重后为 9、5、3、1，第 2 大是 5。）

数据范围

  • \(1 \le n \le 10000\)，\(1 \le k \le n\)，正整数 \(\le 10^9\)

⬇ 点击下载数据包

第 k 大 AC 代码

解题思路

与第 k 小对照：用 greater<int>() 让 sort 降序排列，去重后取第 \(k\) 个。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end(), greater<int>());  // 降序
    a.erase(unique(a.begin(), a.end()), a.end());
    if (k > (int)a.size()) cout << "NO RESULT\n";
    else cout << a[k - 1] << "\n";
    return 0;
}

中位数22

中位数

题目描述

输入 \(n\) 个整数，输出它们的中位数：排序后位于正中间的数；若 \(n\) 为偶数，则取中间两个数的平均（平均数出现 .5 时带小数输出）。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个整数。

输出格式

一个数，为中位数（可能是 x.5 的形式）。

样例输入

1
2
5
4 1 7 2 9

样例输出

1
4

数据范围

  • \(1 \le n \le 10000\)，整数绝对值 \(\le 10^9\)

⬇ 点击下载数据包

中位数 AC 代码

解题思路

排序后取中间：\(n\) 为奇数取第 \((n+1)/2\) 个；偶数取中间两数之和——和为奇数时输出「整数部分 .5」。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());
    if (n % 2) {
        cout << a[n / 2] << "\n";
    } else {
        // 偶数个取中间两数的平均：和为奇数时输出 .5
        long long s = a[n / 2 - 1] + a[n / 2];
        if (s % 2 == 0) cout << s / 2 << "\n";
        else cout << s / 2 << ".5\n";
    }
    return 0;
}

宇宙总统23

宇宙总统

题目描述

全宇宙竞选总统，\(n\) 个人每人获得了一个票数。票数可能非常大（可达 100 位数字）。保证票数互不相同，输出当选总统（票数最大者）的号数与票数。

输入格式

第一行一个整数 \(n\)；接下来 \(n\) 行，每行一个票数（数字串）。

输出格式

两行：第一行为当选者的号数，第二行为其票数。

样例输入

1
2
3
4
3
99
123
98

样例输出

1
2
2
123

数据范围

  • \(1 \le n \le 20\)，票数为不超过 100 位的数字串（互不相同）
宇宙总统 AC 代码

解题思路

票数有 100 位，任何整数类型都存不下——用字符串存票数：先比长度（长的数大），长度相同再比字典序（逐位比大小）。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> v(n);
    for (auto& s : v) cin >> s;
    int best = 0;
    for (int i = 1; i < n; i++) {
        // 票数是大数：先比长度，再比字典序
        if (v[i].size() > v[best].size() ||
            (v[i].size() == v[best].size() && v[i] > v[best]))
            best = i;
    }
    cout << best + 1 << "\n" << v[best] << "\n";
    return 0;
}

超级书架24

超级书架

题目描述

\(N\) 头奶牛叠罗汉去够高度为 \(B\) 的书架顶，第 \(i\) 头奶牛身高 \(H_i\)。选出最少数量的奶牛，使它们的身高之和不小于 \(B\)，输出这个数量。

输入格式

第一行两个整数 \(N, B\)；接下来 \(N\) 行，每行一个整数 \(H_i\)。

输出格式

一个整数，为最少需要的奶牛数。

样例输入

1
2
6 40
6 18 11 13 19 11

样例输出

1
3

数据范围

  • \(1 \le N \le 20000\)，\(1 \le H_i \le 10000\)，\(B\) 不超过所有身高之和
超级书架 AC 代码

解题思路

要奶牛最少，就让最高的奶牛先上——降序排序后从高到低累加，累计和一旦不小于 \(B\) 就输出个数。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, b;
    cin >> n >> b;
    vector<int> h(n);
    for (auto& x : h) cin >> x;
    sort(h.begin(), h.end(), greater<int>());  // 从最高的牛开始叠
    int sum = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        sum += h[i];
        cnt++;
        if (sum >= b) break;                   // 叠到够到书架即可
    }
    cout << cnt << "\n";
    return 0;
}

排序综合

魔法照片25

魔法照片

题目描述

\(n\) 个人（编号 \(1 \sim n\)）各有初始权值 \(W_i\)。将初始权值从大到小排序，得到序号 \(D_i\)（\(1 \sim n\)；权值相同编号小的在前）。类别序号 \(C_i = (D_i - 1) \bmod 10 + 1\)，第 \(i\) 类的人额外获得权值 \(E_i\)。求加成后权值从高到低的前 \(k\) 个人的编号（权值相同编号小的优先）。

输入格式

第一行两个整数 \(n, k\)；第二行 10 个整数 \(E_1 \sim E_{10}\)；第三行 \(n\) 个整数 \(W_i\)。

输出格式

一行 \(k\) 个整数，用空格分隔。

样例输入

1
2
3
5 5
1 2 3 4 5 6 7 8 9 10
10 10 12 13 11

样例输出

1
2 1 3 4 5

数据范围

  • \(1 \le n \le 20000\)，\(1 \le k \le n\)，所有数据在 int 范围内
魔法照片 AC 代码

解题思路

两次排序：第一次按初始权值降序（同值编号小优先）得到名次，按名次取 \(E\) 加成；第二次按加成后的权值降序取前 \(k\) 名（NOIP2016 T1）。

AC代码

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> e(11);                         // E_1..E_10，下标从 1 用
    for (int i = 1; i <= 10; i++) cin >> e[i];
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i++) cin >> w[i];
    // 第一次排序：初始权值降序，同值编号小优先
    vector<int> order(n);
    for (int i = 0; i < n; i++) order[i] = i + 1;
    sort(order.begin(), order.end(), [&](int x, int y) {
        if (w[x] != w[y]) return w[x] > w[y];
        return x < y;
    });
    // 加上类别权值：第 D_i 位（从 1 起）加 E[(D_i-1)%10+1]
    for (int r = 0; r < n; r++) {
        int id = order[r];
        w[id] += e[(r % 10) + 1];
    }
    // 第二次排序：加成后权值降序，同值编号小优先
    sort(order.begin(), order.end(), [&](int x, int y) {
        if (w[x] != w[y]) return w[x] > w[y];
        return x < y;
    });
    for (int i = 0; i < k; i++) cout << order[i] << " \n"[i == k - 1];
    return 0;
}

拼数26

拼数

题目描述

设有 \(n\) 个正整数，将它们连接成一排，组成一个最大的整数。例如 13、312、343 连接的最大整数为 34331213。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个正整数。

输出格式

一个正整数，为拼接出的最大整数。

样例输入

1
2
3
13 312 343

样例输出

1
34331213

数据范围

  • \(1 \le n \le 20\)，\(1 \le a_i \le 10^9\)
拼数 AC 代码

解题思路

把整数当字符串处理，自定义比较器：若 a + b > b + a（两种拼接取大的）则 \(a\) 排前面——注意 312 < 343 但 312343 < 343312，普通数值比较会出错（NOIP1998）。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> v(n);
    for (auto& x : v) cin >> x;
    // 拼接比较：a+b > b+a 则 a 排前面
    sort(v.begin(), v.end(), [](const string& a, const string& b) {
        return a + b > b + a;
    });
    for (auto& x : v) cout << x;
    return 0;
}

双关键字卡片27

双关键字卡片

题目描述

有 \(n\) 张卡片，每张有两个整数：花色（14）与点数（113）。将卡片按花色升序排列，花色相同的按点数降序排列，输出所有卡片。

输入格式

第一行一个整数 \(n\)；接下来 \(n\) 行，每行两个整数：花色与点数。

输出格式

共 \(n\) 行，每行两个整数：花色与点数。

样例输入

1
2
3
4
5
4
2 5
1 13
2 1
1 2

样例输出

1
2
3
4
1 13
1 2
2 5
2 1

数据范围

  • \(1 \le n \le 1000\)，花色为 1 ~ 4，点数为 1 ~ 13

⬇ 点击下载数据包

双关键字卡片 AC 代码

解题思路

自定义比较器写两条规则：花色不同比花色；相同比点数（降序）——多关键字排序的最小模型。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

struct Card {
    int suit, rank;
};

int main() {
    int n;
    cin >> n;
    vector<Card> v(n);
    for (auto& c : v) cin >> c.suit >> c.rank;
    // 花色升序；花色相同按点数降序
    sort(v.begin(), v.end(), [](const Card& x, const Card& y) {
        if (x.suit != y.suit) return x.suit < y.suit;
        return x.rank > y.rank;
    });
    for (auto& c : v) cout << c.suit << " " << c.rank << "\n";
    return 0;
}

排队合影28

排队合影

题目描述

\(n\) 名学生排队合影，排队规则：按身高从矮到高；身高相同的按姓名字典序。输出排好的姓名序列（每行一个）。

输入格式

第一行一个整数 \(n\)；接下来 \(n\) 行，每行为姓名与身高。

输出格式

\(n\) 行，每行一个姓名。

样例输入

1
2
3
4
3
Tom 170
Jerry 165
Ann 170

样例输出

1
2
3
Jerry
Ann
Tom

数据范围

  • \(1 \le n \le 1000\)，姓名长度 \(\le 20\)，身高 \(\le 250\)

⬇ 点击下载数据包

排队合影 AC 代码

解题思路

结构体存（身高、姓名），比较器：身高不同比身高，相同比姓名字典序。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, string>> v(n);            // (身高, 姓名)
    for (auto& p : v) cin >> p.second >> p.first;
    // 身高从矮到高；同高按姓名字典序
    sort(v.begin(), v.end(), [](const pair<int, string>& a, const pair<int, string>& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    });
    for (auto& p : v) cout << p.second << "\n";
    return 0;
}

谁是第二名29

谁是第二名

题目描述

输入 \(n\) 个正整数，求其中严格第二大的整数（相同大小的整数只计算一次；不同的整数不足两个时输出 NO RESULT）。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个正整数。

输出格式

一个整数或 NO RESULT。

样例输入

1
2
6
9 3 9 1 5 5

样例输出

1
5

（去重后为 9、5、3、1，第二大是 5。）

数据范围

  • \(1 \le n \le 10000\)，正整数 \(\le 10^9\)

⬇ 点击下载数据包

谁是第二名 AC 代码

解题思路

降序排序 + 去重后，第二个元素就是严格第二大的值；去重后不足两个输出 NO RESULT。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end(), greater<int>());  // 降序
    a.erase(unique(a.begin(), a.end()), a.end());
    if (a.size() < 2) cout << "NO RESULT\n";
    else cout << a[1] << "\n";                 // 去重后的第二个 = 严格第二大
    return 0;
}

按绝对值排序30

按绝对值排序

题目描述

输入 \(n\) 个整数，按绝对值从小到大排序输出；绝对值相同的按原值从小到大。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个整数。

输出格式

一行 \(n\) 个整数，用空格分隔。

样例输入

1
2
5
-3 2 -5 4 1

样例输出

1
1 2 -3 4 -5

数据范围

  • \(1 \le n \le 1000\)，整数绝对值 \(\le 10^9\)

⬇ 点击下载数据包

按绝对值排序 AC 代码

解题思路

自定义比较器：先比 abs(x) 与 abs(y)；绝对值相同再比原值——abs 函数配合比较器即可。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end(), [](long long x, long long y) {
        if (abs(x) != abs(y)) return abs(x) < abs(y);   // 绝对值升序
        return x < y;                                   // 相同按原值升序
    });
    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
    return 0;
}

  1. 手写冒泡 · 经典入门题（自拟）。 ↩

  2. 手写选择 · 经典入门题（自拟）。 ↩

  3. 手写插入 · 经典入门题（自拟）。 ↩

  4. 计数排序思想 · 经典入门题（自拟）。 ↩

  5. 排序入门 · 经典入门题（自拟）。 ↩

  6. 冒泡交换计数 · 洛谷 P1116。 ↩

  7. 计数排序 · 洛谷 P1271。 ↩

  8. 去重 + 排序 · 洛谷 P1059 · NOIP2006。 ↩

  9. sort() 模板 · 洛谷 P1177。 ↩

  10. 结构体稳定排序 · 经典模板题（自拟）。 ↩

  11. 字符串字典序 · 经典入门题（自拟）。 ↩

  12. 自定义比较器 · 经典模板题（自拟）。 ↩

  13. 结构体最值 · 洛谷 P5740。 ↩

  14. 多关键字 + 稳定性 · 洛谷 P1104。 ↩

  15. 三关键字排序 · 洛谷 P1093 · NOIP2007。 ↩

  16. 排序 + 分数线 · 洛谷 P1068 · NOIP2009。 ↩

  17. 排名计数 · 洛谷 P1428。 ↩

  18. 排序 + 判定 · 洛谷 P1152。 ↩

  19. 排序 + 连续段统计 · 洛谷 P1097 · NOIP2007。 ↩

  20. 去重排序取第 k · 洛谷 P1138。 ↩

  21. 降序取第 k · 经典模板题（自拟）。 ↩

  22. 中位数 · 经典模板题（自拟）。 ↩

  23. 大数字符串比较 · 洛谷 P1781。 ↩

  24. 降序累加 · 洛谷 P2676 · USACO。 ↩

  25. 两次排序 · 洛谷 P1583 · NOIP2016。 ↩

  26. 拼接比较器 · 洛谷 P1012 · NOIP1998。 ↩

  27. 双关键字排序 · 经典模板题（自拟）。 ↩

  28. 身高 + 字典序 · 经典模板题（自拟）。 ↩

  29. 严格第二大 · 经典模板题（自拟）。 ↩

  30. 绝对值比较器 · 经典模板题（自拟）。 ↩