字符串及文件读写

-1 检查浏览器渲染数学公式情况

因为笔者发布文章当天，本博客仍然存在 Latex 可能无法渲染的情况，下面是一个 Latex 示范：

$x$

• 如果正常显示为衡水体 x，则代表读者的浏览器已经成功渲染了 Latex
• 如果显示为 带有美元符号的 x 即 $x$（已除去换行符），则代表读者的浏览器没有成功渲染 Latex，读者可能需要刷新重试，如果刷新多次仍然无法渲染，请尝试换一个浏览器/网络环境

0 框架

你好，这里是 https://www.tropical-fish.cn/，本专题主要讲解 字符串及文件读写，感谢 深入浅出程序设计竞赛（基础篇） 提供的重要支持

这是 C++ 语法基础 的重要补充部分，包括了在 CCF 及其他系列比赛 获得 $\text{非}0$ 分数的方法，注意，这不是危言耸听

$$ \begin{aligned} &\textbf{字符串} \begin{cases} &\text{char}\\ &\text{string}\\ &\text{freopen} \end{cases} \end{aligned} $$

如上面的框架，笔者会介绍

• 字符串的存储
• 字符串的处理方法
• STL 字符串
• 文件输入输出

不废话了，现在开始！

1 char 字符数组

字符数组的 ASCII 本质与常用字符表

字符数组本质上和整数数组并没什么太大的区别，整数数字每一个下标存的是数字，字符数字存的是 字符（其实是 ASCII 码对应的数字），将这些字符存到数组里，便成为了一串字符，即 字符串，下面这张表是 ASCII 表，它们分别将 数字 对应了 字符，读者并不需要记忆全部的内容，仅需要记忆关键的键值，例如 0、A、a、 （空格），它们相对重要

图片

其中的第 $0 \sim 31 \& 127$ 号字符是控制字符，第 $32$ 号字符是空格

在 OI 的场景下，一般只有第 $32 \sim 126$ 号元素起到了相对关键的作用

【题目样本 1.1】P5733 自动修正

题目描述

https://www.luogu.com.cn/problem/P5733

大家都知道，一些办公软件有自动将小写字母转换为大写的功能

输入一个长度不超过 $100$ 且不包括空格的字符串。要求将该字符串中的所有小写字母转换成大写字母并输出

例如输入 Luogu4!, 输出 LUOGU4!

做法 1

分析

既然单个字符可以使用 char 类型存储，那么存储一串字符就可以使用数组，我们可以定义一个数组 $s[]$，其中每一个下标都是字符类型，即 char s[100];，这样的 字符数组 就叫 字符串

读入字符串的办法大同小异

1. 使用 scanf("%s",s);读入一个字符串，其中 %s 代表数据类型，即字符串，s 是定义的字符数组的名字
   至于为什么不需要取地址符 &，因为 s 是一个数组，这里的 s 在大多数表达式中会 自动转换为指向数组首元素的指针，即 &s[0]，类型是 char*，仅此而已
2. 使用 cin>>s;

请 特别注意 这一点，这两种读入方法只能读到空格、换行符、EOF（文章后面会有讲解），至于输入想要包含空格、换行符又想读入到同一个字符数组中，需要使用其他办法，文章后面同样会有讲解

参考代码

这段代码摘取至 深入浅出

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    char s[110];
    scanf("%s", s); // 读入这个字符串，还可以使用 cin>>s; 语句
    for (int i = 0; s[i] != '\0'; i++) // s[i] != '\0' 也有别的方法获取，具体会在文章后面提到
        if ('a' <= s[i] && s[i] <= 'z') /* 如果这个字符在'a'到'z'中间，说明是小写字母 */
            s[i] -= 'a' - 'A'; // 把这个字母转换成对应的大写字母，减去偏移量
    printf("%s\n", s); // 输出这个字符串，还可以使用 cout<<s<<endl; 语句
    return 0;
}

ASCII 码偏移量

这本身并不是一个特有名词，反倒是一个通俗的用语，它的意思由 Deepseek V4 Pro 提供：利用 ASCII 码表中字母的连续编码，通过加减一个固定值（偏移量）来实现大小写转换或字符映射

至于能否听懂，那就因人而异了，下面是一段解释：

如果你认真看了上面的 ASCII 表，你应该会发现 小写字母的顺序和大写字母的顺序分别是按照字母表的顺序排列的，a-A 是小写字母和对应大写字母的 ASCII，这被通俗地认为为 偏移量，这在其他的场景中也有体现，为了缩短篇幅，这里不再阐释，请 特别注意，小写字母的 ASCII 码相对于大写字母大

那么就很好说了，上面的代码利用 if ('a' <= s[i] && s[i] <= 'z') 判断是否是小写字母，如果是，减去偏移量，这样得到的字母就是大写字母了

字符串存储与 \0 结束标记

这段字符串在字符数组中的存储方式如下图

$s[]$ 中的每一个元素，都存储了一个不超过 $127$ 的整数，它们分别对应了 ASCII 编码中的字符

最开始的字符存在 $s[0]$，这个字符串虽然有且仅有 $7$ 个字符，但它却占用了 $8$ 个下标，即 $s[0] \sim s[7]$，字符串的末尾，存了一个特殊的字符 结束标记字符，它是 \0 ，也可能会有 \n 换行符，划掉的原因是因为笔者暂时没有找到任何明确的证据，这个结束标记被用于提示一个字符串的结束位置，它会在修改字符串的时候自动调整，一个例子，我们在用 cout<<s 的时候，结束标记就会告诉 cout 字符串已经没了，提一嘴，类似这样的 “特殊字符”，还有好几个，例如 \n（ASCII 表中可能被表示为 10，划掉的原因同上）

[collapse status="true" title="如何表示 \？"]

#include <bits/stdc++.h>
using namespace std;
int main(){
    cout<<"\\";
}

cout 内的第一个 \ 是转义符，转义后面的字符，因为第二个 \ 转义了 "，为了避免第二个 \ 被转义，所以只好用第一个 \ 转义第二个 \，这样第二个 \ 就不会转义 " 了

控制台输出：

PS D:\Users\Lenovo\Downloads\output> & .\'test.exe'
\

[/collapse]

做法 2

分析

当然，也不用一次直接读入整个字符串，可以每次只读入一个字符，判断是否需要处理，（处理后）输出这个字符即可

这里可以使用 getchar() 函数获取输入中的一个字符，如果你具有好奇心，你可以打开下面的折叠框

[collapse status="true" title="getchar() 的返回类型"]
getchar() 被定义于 cstdio 头文件，因此你需要在使用的时候导入这个头文件

答案：getchar() 返回 int 类型

至于为什么不返回 char，这是因为它要正确处理文件结尾标识符 EOF，后面你就能看见了，马上

因此，尽管你定义了一个 char 类型的变量，调用 getchar() 的时候他会自动根据 ASCII 表转换成 char 类型

这是一个例子：

#include <bits/stdc++.h>
using namespace std;
int main(){
    char s;
    cout<<"请键入一个字符：";
    s=getchar();
    cout<<"您键入的字符是："<<s;
}

PS D:\Users\Lenovo\Downloads\output> & .\'test.exe'
请键入一个字符：s
您键入的字符是：s

[/collapse]

相应的，putchar() 用于输出一个字符

参考代码

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    char s;
    while (1) {
        s = getchar(); // 每次调用 getchar() 函数，读入一个字符
        if (s == EOF)
            break;
        if ('a' <= s && s <= 'z') // 如果这个字符是小写字母
            s += 'A' - 'a'; // 把它转换成大写字母，这样写和上面是一样的
        putchar(s); // 调用 putchar() 函数，输出一个字符
    }
    return 0;
}

输入结束和 EOF

运行程序，结果发现无论输入什么，程序都没有反应，这是因为程序不认为输入已经结束了，继续在等待输入

遇到这种情况，输入完字符串后，按一下 Ctrl+Z 组合键，再按一次回车，就可以完成读入了

程序中读入一个字符都会判断是否读完了整个文件，如果文件被读完了，那么 getchar() 函数会返回 EOF（一个特殊的常量)，即 End of File，这标志着读入已经结束了

在控制台中可以使用 Ctrl+Z 组合键（Windows 下）或者 Ctrl+D 组合键（Linux 下）来输入 EOF 标记提示程序输入已经完毕

至于一些教材使用的 gets() 函数将字符串读入字符数组，由于存在字符数组越界的风险， 已经不再建议使用，新的 C++11 标准更是删除了这个函数

而输出一个字符串还可以使用 puts() 方法，同时会自动输出换行，这倒是还能使用

如果您了解 HUSTOJ，您应该会遇到 #define gets(S) fgets(S,sizeof(S),stdin)，仅仅提一嘴

【题目样本 1.2】P1914 凯撒密码

题目描述

https://www.luogu.com.cn/problem/P1914

凯撒密码是由原文字符串（由不超过 $50$ 个小写字母组成）中每个字母向后移动 $n$ 位形成的

z 的下一个字母是 a，如此循环

给出 $n$ 和移动前的原文字符串，请求出密码

分析

你可以导入这个字符串，一个一个处理，然后输出

你需要注意，你不能直接给每一位加上 $n$ 然后输出，因为可能会溢出，举一个例子，一个字符串是 $\text{z}$，$n=5$，如果直接加上答案就是 $\text{DEL}$（$127$），如果不清楚这是什么，请翻阅前面的 ASCII 表，很明显答案是错的

所以，我们应该使用 s[i]-'a' 来计算和 $\text{a}$ 的偏移量，然后加上 $n$，得到目标字母的位置，一个例子，$\text{b}$ 这个字母移动 $4$ 位，就是第 $1$ 个字母（$\text{a}$ 是第 $0$ 个字母）向右移动 $4$ 位，是第五个字母，即 $\text{f}$

为了要求这个位置始终在 $0 \sim 25$ 之间，我们应当把上一段计算除的结果对 $26$ 取模，后面还需要再加上 $\text{a}$，以还原为字母，记 s[i]-'a' 为 $t$，则计算的答案为 $(t \bmod 26)+\text{a}$

警告：读者应当理解 $a$ 与 $\text{a}$ 的区别，第一个指的是字母，第二个指的是值

参考代码

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    int n;
    char s[60];
    scanf("%d %s", &n, s);    // 读入字符串
    for (int i = 0; s[i] != '\0'; i++)
    putchar((s[i] - 'a' + n) % 26 + 'a');    // 计算偏移量并还原
    return 0;
}

【题目样本 1.3】P1125 [NOIP 2008 提高组] 笨小猴

题目描述

给出一个单词（由不超过 $100$ 个小写字母组成），假设 $maxn$ 是单词中出现次数最多的字母的出现次数，$minn$ 是单词中出现次数最少的字母的出现次数，如果 $maxn-minn$ 是一个质数，那么笨小猴就认为这是个 $\text{Lucky Word}$，输出 Lucky Word，然后在第二行输出 maxn-minn 的值；否则输出 No Answer，第二行输出 0

分析

考虑 计数排序思想，读入一个字母，用 $f[]$ 数组记录 $a \sim z$ 字母出现的数量，可以转换成 $0 \sim 25$ 的数字但是直接存更方便，$f[]$ 数组的大小为 $129$，这是 ASCII 表 非拓展字符的值域，随后使用 打擂台 思想寻找出现 次数最多的字母 和 非 $0$ 的最少，判断差是否为质数

bool isPrime(int n) { // 判断质数
    // 小于2的数不是质数
    if (n < 2) {
        return false;
    }
    
    // 从2到n-1逐个试除
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;  // 能被整除，是合数
        }
    }
    
    return true;  // 都不能整除，是质数
}

[collapse status="false" title="判断质数极限方法"]

inline uint64_t isqrt_u64(uint64_t n) { // 判断质数：小数字用试除（快），大数字用 Miller-Rabin（更快）
    if (n < 2) return n;
    uint64_t x = n;
    uint64_t y = (x + 1) >> 1;
    while (y < x) {
        x = y;
        y = (x + n / x) >> 1;
    }
    return x;
}

inline uint64_t mod_mul(uint64_t a, uint64_t b, uint64_t mod) {
    return (__uint128_t)a * b % mod;
}

inline uint64_t mod_pow(uint64_t a, uint64_t d, uint64_t mod) {
    uint64_t res = 1;
    while (d) {
        if (d & 1) res = mod_mul(res, a, mod);
        a = mod_mul(a, a, mod);
        d >>= 1;
    }
    return res;
}

bool isPrime(uint64_t n) {
    if (n < 2) return false;
    if (n == 2 || n == 3 || n == 5 || n == 7) return true;
    if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false;
    
    // 小数字用试除（更快）
    if (n < 1000000000ULL) {
        uint64_t limit = isqrt_u64(n);
        for (uint64_t i = 11; i <= limit; ) {
            if (n % i == 0) return false;
            if (n % (i + 2) == 0) return false;
            if (n % (i + 6) == 0) return false;
            if (n % (i + 8) == 0) return false;
            if (n % (i + 12) == 0) return false;
            if (n % (i + 18) == 0) return false;
            if (n % (i + 20) == 0) return false;
            if (n % (i + 26) == 0) return false;
            i += 30;
        }
        return true;
    }
    
    // 大数字用 Miller-Rabin
    uint64_t d = n - 1;
    int s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }
    
    static const uint64_t bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (uint64_t a : bases) {
        if (a >= n) continue;
        uint64_t x = mod_pow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int r = 1; r < s; r++) {
            x = mod_mul(x, x, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

具体内容不解释，自行搜索

上述内容取自 Deepseek V4 Pro
[/collapse]

如果有需要，可以封装成 namespace

参考代码

同样取自 深入浅出

#include <stdio.h>
#include <iostream.h>
#include <string.h>
using namespace std;

int main() {
    char a[110];
    int ans[26] = {0};              // ans[0] 到 ans[25] 分别代表 'a' 到 'z' 出现的次数，注意要初始化
    int l, mmax, mmin, delta;       // 字符长度，出现次数最多的字母出现次数和出现次数最少的字母出现次数，以及差值

    scanf("%s", a);
    l = strlen(a);

    for (int i = 0; i < l; i++) {
        ans[a[i] - 'a']++;          // 统计增加某个字母的数量
    }

    mmax = 0;
    mmin = 10000;                   // 最大最小值初始化

    for (int i = 0; i < 26; i++) {  // 寻找每个字母的最大值和最小值
        if (ans[i] > mmax) {
            mmax = ans[i];          // 如果超过最大值
        }
        if (ans[i] != 0 && ans[i] < mmin) {
            mmin = ans[i];          // 如果小于最小值，但是不能为 0
        }
    }

    delta = mmax - mmin;

    if (delta == 0 || delta == 1) { // 质数特判
        printf("No Answer\n0\n");
        return 0;
    }

    for (int h = 2; h * h <= delta; h++) {  // 枚举质数
        if (delta % h == 0) {
            printf("No Answer\n0\n");       // 直接输出答案并退出程序
            return 0;
        }
    }

    printf("Lucky Word\n%d\n", mmax - mmin);
    return 0;
}

string 头文件

这是一个前所未有的新头文件，它包含了一些新的头文件

这里有一些新的用法，供读者参考：

• size_t strlen(const char *s); 求 char 数组的长度，将要求长度的数组放进 () 之中，在大部分情况下被 typedef 定义为 unsigned int，这也是为什么你在用 for(int i=0;i<strlen(s);i++) 会报 Warn 的原因，类型不同
• char *strcpy(char *dest, const char *src); 将 *str 复制到 *dest，即复制字符串，返回值一般无用

• int strcmp(const char *s1, const char *s2); 判断两个字符数组是否相同，下面是返回值及意义

  • $=0$ 是 $s1$ 和 $s2$ 完全相同
  • $\lt 0$ 是 $s1$ 小于 $s2$
  • $\gt 0$ 是 $s1$ 大于 $s2$

字符数组不能直接复制一个字符串，因为字符数组中的数组名也只是一个数组名，上面提供的函数可能会有作用

但是 char a[100]="TropicalFish"; 是合法的

【题目样本 1.4】P1957 口算练习题

题目描述

https://www.luogu.com.cn/problem/P1957

王老师收集了 $i(i \leq 50)$ 道学生经常做错的口算题，并且想整理编写成一份练习

王老师希望尽量减少输入的工作量，比如 $5+8$ 的算式最好只输入 5 和 8，输出的结果要尽量详细以方便后期排版使用

对于上述输入进行处理后，输出 5+8=13 以及该算式的总长度 6

输入数据第 $1$ 行是 $i$，接着的 $i$ 行是需要输入的算式，每行可能有 $3$ 个数据或两个数据

• 若该行是 $3$ 个数据，则第一个数据表示运算类型，a 表示加法运算，b 表示减法运算，c 表示乘法运算，接着的两个数据表示参加运算的运算数
• 若该行是两个数据，则表示本题的运算类型与上一题的运算类型相同，而这两个数据为运算数

分析

笔者写到这里的时候，就比较随意了，因为本题没有多大的实际意义，一般地，它只是作为一道相对复杂的应用题/模拟题

在本题中 switch-case 相对于 if-else 更加方便

sscanf 与 sprintf

他们的作用都是从字符串中读入/写出

请区别 scanf 与 printf

参考代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
    int n, a, b, c;
    char last, s[20], ans[20];
    scanf("%d\n", &n);
    while (n--) {
        fgets(s, sizeof(s), stdin); // 读入一行
        if (s[0] == 'a' || s[0] == 'b' || s[0] == 'c')
            last = s[0], s[0] = ' '; // 获取计算符号，并替换为空格
        sscanf(s, "%d %d", &a, &b); // 从这个字符串里面读入两个数 a 和 b 
        switch (last) {
            case'a': c = a + b; sprintf(ans, "%d+%d=%d", a, b, c); break; // +
            case'b': c = a - b; sprintf(ans, "%d-%d=%d", a, b, c); break; // -
            case'c': c = a * b; sprintf(ans, "%d*%d=%d", a, b, c); break; // ×
        }
        printf("%s\n%d\n", ans, strlen(ans)); // 输出
    }
    return 0;
}

上面的代码同样改编于 深入浅出

2 string 字符串

从 C 风格字符串到 C++ STL 的 string 类型

$$ \left\{ \begin{array}{l} \textbf{C++ 标准库} \\ \left\{ \begin{array}{l} \textbf{STL（标准模板库）} \\ \left\{ \begin{array}{l} \text{容器} \left\{ \begin{array}{l} \text{vector} \\ \text{list} \\ \text{map} \\ \boxed{\text{string}} \quad \text{（核心问题）} \end{array} \right. \\ \text{迭代器} \\ \text{算法} \\ \text{适配器} \\ \text{分配器} \\ \text{函数对象} \end{array} \right. \\ \text{其他组件} \left\{ \begin{array}{l} \text{I/O 流} \\ \text{异常处理} \\ \text{内存管理} \end{array} \right. \end{array} \right. \end{array} \right. $$

上面的思维导图由 Deepseek V4 Pro 生成，它体现了 string 与 STL 的主要关系

很明显的，使用 C 语言的字符数字有很多不便（char 是属于 C 语言的），比如 不能：

• 弹性变化长度
• 直接赋值
• 直接复制
• 有数组越界的风险（gets）

好消息是，C++ 中提出了 STL 这一概念，即 标准模板库，将很多有用的功能进行了封装，直接就可以用，不需要重新开发这些功能，我们为 2017 年的 OI 选手默哀，已经封装的功能包括但不限于：

• 栈（stack）
• 队列（queue）
• 排序（sort）

总的来说，封装了容器、算法、其他功能，现在，我们会使用 string 解决字符串问题

【题目样本 2.1】P5015 [NOIP 2018 普及组] 标题统计

题目描述

https://www.luogu.com.cn/problem/P5015

凯凯刚写了一篇美妙的作文，请统计这篇作文的标题中有多少个字符

注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符，且字符串中的字符和空格数总和不超过 $5$

统计标题字符数时，空格和换行符不计算在内

分析

因为使用 cin 读入字符串时会忽略空格，并且读到 空格 或者 换行符 就停止了，所以可以将读入写进 while() 中，每次读入一个字符串，把长度加入答案即可

至于读入整行，会在 【题目样本 2.3】 中给出方法

参考代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    int ans = 0;
    while (cin >> s)
        ans += s.length();
    cout << ans << endl;
    return 0;
}

深入浅出

string：字符串的加强版数据类型

这里没使用 char，而是使用了一种新的数据类型 string，一个 string 类型的变量可以用来存储一个字符串，还可以把这个字符串当成一个整体的处理，string 的功能包括但不限于：

• 赋值
• 拼接
• 裁剪

char 毕竟是个数组，能做到这些就很烦了

输人时使用 cin 语句，不断读入字符串

当发现读入文件读完后（遇到 EOF，可以按 Ctrl+Z 组合键），cin>>s 本身就会返回 $0$，中断 while 语句，结束读入

这里的 $s$ 变量可以被认为是一个“加强版“的字符数组，可以使用 s.length()（s.size()） 来直接查询字符串 $s$ 的长度，也可以和字符数组一样使用 $s[0]$ 来查询这个字符串最开头的字符是什么

更厉害的是，string 类型的字符串可以直接拿来赋值、拼接操作，比如 s=s+s 就是将两个字符串 $s$ 拼接在一起，其结果赋值回 $s$ 的意思，请注意，这里提到的代码操作的时间复杂度是 $O(n)$，建议写 s+=s（s.append(s) 会在 【题目样本 2.2】 提到）

上述描述操作的便利性可不是字符数组可以比较的

【题目样本 2.2】P5734 文字处理软件

题目描述

https://www.luogu.com.cn/problem/P5734

现在需要开发一款文字处理软件

最开始时输入一个字符串（不超过 $100$ 个字符）作为初始文档

可以认为文档开头是第 $0$ 个字符，需要支持以下操作

1. 1 str: 后接插入，在文档后面插入字符串 $\text{str}$，并输出文档的字符串
2. 2 a b: 截取文档部分，只保留文档中从第 $a$ 个字符起 $b$ 个字符，并输出文档的字符串
3. 3 a str: 插入片段，在文档中第 $a$ 个字符前面插入字符串 $\text{str}$，并输出文档的字符串
4. 4 str: 查找子串，查找字符串 $\text{str}$ 在文档中最先出现的位置并输出；如果找不到输出 -1

为了简化问题，规定初始的文档和每次操作中的 $\text{str}$ 都不含有空格或换行

最多会有 $q (q \leq 100)$ 次操作

例如输入数据是：

4
ILove
1 Luogu
2 5 5
3 3 guGugu
4 gu

那么输出数据是：

ILoveLuogu
Luogu
LuoguGuuguugu
3

保证每次操作输入的字符串长度不超过 $100$ 且输入合法（($2$) 和 ($3$) 操作不会越界）

分析

string 需要头文件 string，方法包括但不限于：

1. string s: 定义一个名字为 $s$ 的字符串变量
2. s += str 或 s.append(str): 在字符串 $s$ 后面拼接字符串 $\text{str}$
3. s < str: 比较字符串 $s$ 的字典序是否在字符串 $\text{str}$ 的字典序之前
4. s.size() 或 s.length(): 得到字符串 $s$ 的长度
5. s.substr(pos, len): 截取字符串 $s$，从第 $pos$ 个位置开始 $len$ 个字符，并返回这个字符串
6. s.insert(pos, str): 在字符串 $s$ 的第 $pos$ 个字符之前，插入字符串 $\text{str}$，并返回这个字符串
7. s.find(str, [pos]): 在字符串 $s$ 中从第 $pos$ 个字符开始寻找 $\text{str}$，并返回位置，如果找不到返回 $-1$，$pos$ 可以省略，默认值是 $0$

灵活地运用上面的这些办法，可以使笔者更好地玩此题目

额外需要注意：s.find() 在 无法找到 时，会返回 string::npos，因此，你可以利用 s.find("bqiu")!=string::npos 判断 $s$ 中是否包含 $\text{bqiu}$，如果包含，返回 $1$，反之 $0$

string 的赋值

string a, b;
a="bqiu";
b=a;

上面的代码完全可以通过编译

但是 char 不行

【题目样本 2.3】P1308 [NOIP 2011 普及组] 统计单词数

题目描述

https://www.luogu.com.cn/problem/P1308

给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置

注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同，如果给定单词仅是文章中某一单词的一部分则不算匹配

分析

s.find() 是一个好东西

请注意，若 $s$ 为 $\text{to be or not to be is a question}$，在搜索 $\text{tion}$ 时，是否会检索到包含单词 question？

因此，你可以搜索 tion ，全字匹配

如果你这样做，你可能会意识到这个问题，如果 tion 在文章的结尾怎么办？

我们可以将 $s$ 的前后加上空格，即 s=' '+s+' '，这样就可以方便地解决这个问题

你太牛逼了

至于统计次数，你可以记下 find() 每次的返回值（位置），然后将位置作为参数继续查找，直到找到了 string::npos 就可以完成，这就是找到了多少次

getline：整行读入

为了方便地读取整行字符串，不用被 cin 的傻逼特性干扰，我们可以使用 getline() 函数，它的作用是将完整的一行的输入数据读入（到字符串中），一般地，它的用法是 getline(cin,<string_name>)，<string_name> 指 string 字符串的名字

string：其他

下面的这一个代码，体现了 string 具有强大的扩展性

// string 转字符数组
char arr[10];
string s = "LUOGU";
int len = s.copy(arr, 9); // 最多允许复制 9 个字符，否则就越界了
arr[len] = '\0'; // 在末尾增加结束标记

// 或者
char arr[10];
string s = "LUOGU";
strcpy(arr, s.c_str()); // strncpy(arr, s.c_str(), 10);

// 字符数组转 string 就更简单了
char arr[10];
strcpy(arr, "LUOGU");
string s;
s = arr;

在这里表示对 DeepSeek 的尊敬！

3 freopen 文件操作

废话

直到现在为止，绝大部分的输入输出方式都是 标准输入输出，即 stdin 与 stdout

但在很多程序设计竞赛中，例如万恶的 CCF，它们要求使用文件输入输出，这种输入输出的方式，可以将硬盘上的文件读入到程序，将程序中的输出写入到硬盘，Linux 中的 < 和 > 重定向符号和这个是一个道理，如果你没有在竞赛中使用文件读写，你会获得一个最小的自然数的分数

题目样本

题目描述

https://www.tropical-fish.cn/usr/uploads/2026/08/1163827895.pdf

分析

这是 $\text{2024 CCF 非专业级软件能力认证 CSP-J/S 2024 第二轮认证}$ 的真题，请看试题卷 题目 A poker

这道题是一道非常简单的模拟题，参考代码如下

#include <bits/stdc++.h>
using namespace std;
int T,ans;
string s;
map <string,int> f;
int main(){
    cin>>T;
    while(T--){
        cin>>s;
        if(!f[s]) ans++,f[s]=1;
    }
    cout<<52-ans;
}

但是，如果读者直接将这个代码作为你的程序提交，你会获得 0 分的好成绩，请看试题卷第一页，它给出了 英文题目与子目录名、提交源程序文件名、可执行文件名、输入文件名、输出文件名，我们必须按照这个要求使用，虽然其他信息也相对重要，但是就文章标题而言，没那么重要

根据要求，我们应当将文件保存为 /<英文题目与子目录名>/<提交源程序文件名>，也就是 /poker/poker.cpp，然后，我们需要学会使用 freopen，下面是一个比较基础的用法

freopen("<read_file_name>","r",stdin);
freopen("<write_file_name>","w",stdout);

一般它会放在 main 函数的下面

也就是说，这题的代码需要改成：

#include <bits/stdc++.h>
using namespace std;
int T,ans;
string s;
map <string,int> f;
int main(){
    freopen("poker.in","r",stdin);
    freopen("poker.out","w",stdout);
    cin>>T;
    while(T--){
        cin>>s;
        if(!f[s]) ans++,f[s]=1;
    }
    cout<<52-ans;
}

本地运行后，发现程序一闪而过，啥也没有，反倒程序文件目录出现了一个 poker.out

既然它有读入文件，我们就应当给程序指定输入文件 poker.in，可以将题目的输入样例填写进去，运行，就发现 poker.out 有了答案

特别的，当程序读到 EOF 时，就会停止输入（相当于 ^Z）

如果是在一般的 Online Judge 提交上面的代码，会判为 WA，如果 OJ 没有要求指定输入输出文件名（一般没写就是没有），所以，我们应当删除 freopen 或者设为注释行

重要：文件名等信息必须与题目要求的一模一样！复制粘贴是一个好东西

Better

如果你为了在撰写代码时的快速，你可以只注释 输出文件 的 freopen，这样，在 输入文件 填写好测试数据之后，运行即可看到结果，相对于下面的方法快多了

• 都不注释，你需要每次看 输出文件，很烦
• 都注释，你需要每次粘贴样例，而且对于多组测试数据的试题更加繁琐

4 总结

$Thanks \space for \space reading.$

排序（Round 1）

-1 检查浏览器渲染数学公式情况

因为笔者发布文章当天，本博客仍然存在 Latex 可能无法渲染的情况，下面是一个 Latex 示范：

$x$

• 如果正常显示为衡水体 x，则代表读者的浏览器已经成功渲染了 Latex
• 如果显示为 带有美元符号的 x 即 $x$（已除去换行符），则代表读者的浏览器没有成功渲染 Latex，读者可能需要刷新重试，如果刷新多次仍然无法渲染，请尝试换一个浏览器/网络环境

0 框架

在本文中，我将重点介绍 排序，感谢 深入浅出程序设计竞赛（基础篇） 提供重要支持，本文有一部分的内容是基于本书修改

排序 是在 OI 算法中重要的一部分，虽然大部分场景下都可以用 sort 解决（限于 bits/stdc++.h），但是掌握具体的内容还是必不可少的，相对于初赛而言

$$ \begin{aligned} &\textbf{排序（Round 1）} \begin{cases} &\text{计数排序}\\ &\text{选择排序、冒泡排序、插入排序}\\ &\text{快速排序}\\ &\text{排序算法的应用}\\ &\text{汇总}\\ \end{cases} \end{aligned} $$

1 计数排序

【题目样本 1.1】P1271【模板】排序

题目描述

https://www.luogu.com.cn/problem/P1271

学校正在选举学生会成员，有 $n(n \leq 999)$ 名候选人，每名候选人编号分别从 $1$ 到 $n$, 现在收集到了 $m(m \leq 200000)$ 张选票，每张选票都写了一个候选人编号

现在想把这些堆积如山的选票按照投票数字从小到大排序。输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字，求出排序后的选票编号。例如，当有 $5$ 个候选人，$10$ 张选票分别是 $2、5、2、2、5、2、2、2、1、2$ 时，需要输出 1222222255

分析

这题本质有很多方法，但是由于是 计数排序，因此：

在投票区放上 $n$ 个投票箱，投票人支持谁就把票投入对应的投票箱中，投票后只须统计每个投票箱有几张选票，直接按照候选人编号取出来就可以完成排序操作

也不需要排序了

参考代码

#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,x,f[100005];
int main(){
    cin>>n>>m;
    for(i=1;i<=m;i++) cin>>x,f[x]++;
    for(i=1;i<=n;i++) for(j=1;j<=f[i];j++) cout<<i<<" ";
}

这里倡导数组从 $1$ 开始存

只需要开一个大小不小于 $n$ 的数组作为票箱，依次读入选票，然后将选票号数加到对应的票箱中，最后按照每个票箱的数量输出候选人编号即可

在这个过程中，甚至不需要存储下每一张选票

在完成输入并计算时，$f[]$ 状态如下

计数排序

这种排序方法被称为 计数排序

读入选票并统计的时间复杂度是 $O(m)$，输出选票的时间复杂度是 $O(m+n)$（第一层循环做 $n$ 次，$f[i]$ 至多为 $m$），空间复杂度是 $O(n)$（因为 $f[]$）

所以计数排序只能用于排序编号范围不是很大的数字，如果需要排序的数字要到 $10^9$，别说运行时间了，内存都无法存得下这么大的范围的数组

此外，如果希望将一些浮点数或者字符串进行排序，就没办法去建造合适的 投票箱，所以就不能使用这种算法了（把下标存成 $\text{浮点数} \times 10^\text{浮点数位数}$ 也是一个不错的选择）

也有改进方法，即 桶排序&基数排序，思路类似，但是复杂

无论是上段和计数，这些排序都是基于分类，并非比较

2 选择排序、冒泡排序、插入排序

【题目样本 2.1】数列排序

题目描述

输入 $n(n \leq 1000)$ 个数字 $a_i(a_i \leq 10^9)$, 将其从小到大排序后输出

分析

设有 $5$ 张纸牌，他们是 $4,1,9,5,1$，打牌时如何排序？

解法 1：选择排序

分析

求最大值：max()

求最小值：min()

求一序列最值：for(int i=1;i<n;i++) ma=max(ma,a[i]);，a[] 为序列，$n$ 为数量，$ma$ 存放最大值

核心思想：打擂台

如何联想到本题？

[collapse status="false" title="答案"]
从第一张牌到最后一张牌中找到最小的一张，放在最前面的位置；然后从第二张牌到最后一张牌中继续找到最小的一张，放到第二位……如此反复，就可以得到从小到大的序列
[/collapse]

这里有一张不错的图，来自 深入浅出，因此贴在这

若遇到大小相等的牌，continue

参考代码片段

for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++)
        if (a[j] < a[i]) {
            int p = a[i];
            a[i] = a[j];
            a[j] = p;
        }
}

解法 2：冒泡排序

分析

如果尝试把最大的一项放在后面，虽然可以倒过来使用选择排序，但是可以试试别的办法

这里有一张图，来自 豆包，它打了一个类似于文章的比方，讲述了 选择排序 与 冒泡排序 的区别，前情提要是 现有扑克牌：9、5，要排成5、9

首先比较第 $1$ 张牌和第 $2$ 张牌，如果后面的牌比前面的牌小，那么就交换位置；然后比较第 $2$ 张牌和第 $3$ 张牌，同样保证第 $3$ 张牌要大于第 $2$ 张牌……依此类推， 直到比较最后一张牌和倒数第二张牌，这样就能保证最后面的一张牌是最大的一张了

继续进行新的一轮，利用上面一样的交换，但是需要注意的是，由于最后一张牌已经是手牌中最大的一张了，所以只需要比较到倒数第二张就行了

这一轮后结束后倒数第二张牌就是第二大的牌（当然，也有可能是并列最大)。经过 $n-1$ 轮排序后，就得到了有序的手牌

下图同样来自 深入浅出，用于理解

参考代码片段

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++)
        if (a[j] > a[j + 1]) {
            int p = a[j];
            a[j] = a[j + 1];
            a[j + 1] = p;
        }
}

[scode type="green"]
int p=a[j];a[j]=a[j+1];a[j+1]=p; 推荐用 swap(a[j],a[j+1]); 来取代，用于交换
[/scode]

解法 3：插入排序

分析

一种很形象的比喻

你在玩纸牌游戏的时候，从牌堆里面抽牌，抽到一张牌，放到你的手牌里，你是怎么保证手牌内的牌是有序的呢？

如果你能通过 Cloudflare 的人机验证，你应该会看看抓到牌的大小，再看看手牌，定位到合适的位置，插入

上面描述的过程，即 插入排序

1. 把手牌分为有序的和无序的两部分
2. 最开始有序的就只有一张牌，也就是第一张
3. 要把接下来的 无序区 中的一张牌（称为 待插牌 ）插入到 有序区 中，就是从有序区的末尾开始往前比较，如果待插牌比正在比较的牌小，那么就把有序区的正在比较的牌往后面放一格，然后继续往前面进行比较，直到待插牌遇到不大于自己的牌或者成为第一个为止
4. 这时，待插牌就可以填入留出来的缺口中。反复将无序区中的待插牌插入到有序区中，直到所有的牌都在有序区

同样的，这里有一张非常生动的图，供读者查阅

下面这是来自 深入浅出 的 插入排序 实现代码，进行了注释的补充

for(int i = 1; i < n; i++) {
    int now = a[i], j;          // 记录待插入元素，稍候会放进去
    for(j = i - 1; j >= 0; j--) // 一个很经典的模板：元素后移
        if(a[j] > now)
            a[j + 1] = a[j];    // 大于now的元素后移
        else
            break;
    a[j + 1] = now;             // 插入到正确位置
}

选择排序

为了加强读者的记忆，这里重新梳理一遍

解法 1 这种算法被称为 选择排序

从代码中可以看出有两重循环，读者可以自己计算一下已知 $n$ 的情况下一共需要比较的次数

选择排序的算法时间复杂度是 $O(n^2)$；由于只需要一个数组存下这些数字即可，空间复杂度是 $O(n)$

[collapse status="false" title="答案"]

$$ \frac{n(n-1)}{2} $$

[/collapse]

冒泡排序

解法 2 这种算法被称为 冒泡排序，在一轮中，最大的那张牌会一点一点地从左移动到右边，像冒泡泡一样

读者也可以计算一下排序的过程中需要进行几次比较

冒泡排序算法的时间复杂度也是 $O(n^2)$，空间复杂度也是 $O(n)$

冒泡排序相比于选择排序并没有实质性的改进

有一种冒泡排序的改良版叫作希尔排序，不是相邻位置的两个数字比较，而是比较距离更远的两个数字，虽然能略微优化一些复杂度，但依然不实用

猴子排序同样也是一种奇怪的办法

插入排序

这种算法叫作 插入排序

如果序列本来已经从小到大排序，那么每次无序区的待插牌都不会插进有序区中，而是紧贴在有序区后使有序区一直扩大，那么只需要 $n-1$ 次比较就可以完成算法流程

然而，如果序列是从大往小排序，那么每次插入都会将有序区中的所有牌往后面挪动一次，这样速度就非常慢了

讲时间复杂度一般会考虑最悲观的情况，所以插入排序的算法复杂度还是 $O(n^2)$，和选择排序、冒泡排序的复杂度一致，它们空间复杂度也是一样的

不过，如果能保证序列 基本有序 , 那么使用插入排序的效率可能会不错

不推荐在 Contest 中使用这些方法，耗时过久

笔者认为，学习这些是为了掌握原理，在第一轮比赛中获得较好的成绩，在历年的 OI 比赛中，有相当一部分的套题涉及了这个内容

3 快速排序

【题目样本 3.1】P1177 快速排序

题目描述

https://www.luogu.com.cn/problem/P1177

输入 $n(n \lt 10^5)$ 个数字 $a_i(a_i \lt 10^9)$，将其从小到大排序后输出

分析

这个数据量就很大了，插入排序、选择排序、冒泡排序都无法完成。这次将介绍在 OI 中最普遍使用的排序算法 快速排序，简称快排，顾名思义

快速排序说起来其实也挺简单的，但是需要读者能够理解递归

[collapse status="false" title="递归"]
递归就是函数调用自己。

你的快速排序就是递归：

void Qsort(int x, int y) {
    if (x >= y) return;          // 终止条件
    // ... 分区操作 ...
    Qsort(x, i);                 // 自己调用自己，排左边
    Qsort(i+2, y);               // 自己调用自己，排右边
}

执行过程：先把数组分成左右两部分，然后分别对两部分再调用同样的函数继续分，直到每部分只剩一个元素。

每次调用会占用栈内存，递归太深会栈溢出。你的代码最坏情况（已有序数据）递归深度达 $200000$，风险很大。

上述内容来自 Deepseek V4 Pro，请注意辨别
[/collapse]

算法的大致过程是对于一个无序序列，找到一个 哨兵数 ，将序列中所有比哨兵数小的数字都在哨兵数的左边，所有比哨兵数大的数字都在哨兵数的右边；然后分别对哨兵数左边和右边再使用同样的方法找到新的哨兵数，并再次进行分类，直到集合不可分割为止

怎么选择哨兵呢？随便选，可以是第一个，可以是中间那个，也可以在序列中随机选择

选择好哨兵，然后从序列左端开始寻找第一个比哨兵大的数字，从右边选择第一个比哨兵小的数字，然后交换这两个数；接着继续从左边找到比哨兵大的数字，右边比哨兵小的数字并交换……直到将序列分为两组，左边序列都不大于哨兵，右边序列都不小于哨兵，就可以分别对左边和右边进行排序了

下面同样还有一张生动的图，建议配合代码食用

参考代码

有多种办法可以实现，这是一种实现办法，也基于书本内容进行了适当的补充更多的办法请前往 排序的应用 这一章节

void qsort(int a[], int l, int r) { // a[] 传递数组
    int i = l, j = r, flag = a[(l + r) / 2], tmp;  // flag是基准值（哨兵）
    do {
        while (a[i] < flag) i++;   // 左指针右移，跳过比基准小的
        while (a[j] > flag) j--;   // 右指针左移，跳过比基准大的
        if (i <= j) {              // 找到一对需要交换的数
            tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++; j--;              // 继续移动指针
        }
    } while (i <= j);              // 两指针未交错就继续
    if (l < j) qsort(a, l, j);     // 递归排左半部分
    if (i < r) qsort(a, i, r);     // 递归排右半部分
}

快速排序

虽然在极端情况下（比如数列已经有序，且每次选择哨兵都会分出长度为 $1$ 的小段），快速排序的时间复杂度是 $O(n^2)$，但是如果随机选择哨兵，则很难出现这种情况

实际上，随机化快速排序的算法复杂度是 $O(n \log n)$，空间复杂度是 $O(n)$，而且不需要额外的辅助空间，所以是一种最为实用的排序算法

快速排序利用了 分治 思想，后面可能会出一篇 排序 这一专题的补充篇，介绍了更多的非基础排序

额外的，二分查找法 也利用了 分治思想，这个方法也可能会在未来单独出一篇专题进行讲解

【题目样本 3.2】 P1923 求第 $k$ 小的数

题目描述

https://www.luogu.com.cn/problem/P1923

输入 $n(n \lt 10^6 \text{ 且 } n \text{ 为奇数})$ 个数字 $a_i(a_i \lt 10^9)$，输出这些数字的第 $k$ 小的数，最小的数是第 $0$ 小

分析

如上 URL 中的 题目描述，如果你是真的要训练 快排，请 不要 使用 nth_element STL，当然我估计你也不知道

虽然可以直接排序，然后取数组中的第 $k$ 个作为答案进行输出，但是直接排序一遍的复杂度是 $O(n \log n)$，不适合这道头目，我们可以借鉴 快排 的 分治思想 把时间复杂度降至 $O(n)$

[collapse status="false" title="可以降低时间复杂度的原因"]

核心原因在于每次只需要递归处理一边，而不是两边

更多的：

1. 快速排序的分治过程
   每次选一个基准（pivot），将数组分成三部分：

   • 左边：所有元素 ≤ pivot
   • 中间：pivot 本身
   • 右边：所有元素 > pivot

   然后递归地对左右两边分别排序，所以总复杂度是 (O(n \log n))。

2. 求第 k 小数的优化
   在快速选择（Quick Select）中，不需要对两边都排序，只需要判断第 k 小的数在哪一边：

   • 如果 (k) 小于左边元素个数，就只在左边递归查找
   • 如果 (k) 等于左边元素个数 + 1，那么 pivot 就是答案
   • 否则，只在右边递归查找，并且调整 k 的值

3. 复杂度分析

   • 每次递归处理的数组大小大约是上一次的一半（平均情况）

   • 总比较次数：

     $$ n + \frac{n}{2} + \frac{n}{4} + \cdots = 2n $$

   • 因此平均时间复杂度是 (O(n))

上述内容来源 Deepseek V4 Pro 修改而得
[/collapse]

和快速排序的方法一样，任意取一个哨兵，将序列分为两部分，左边部分的所有数字都不大于右边的数字

• 如果 $k$ 在左边的范围，则递归求解左边的部分
• 如果在右边，则递归求解右边的部分
• 但是也有可能两边都不属于（比如说 $j=4$ 而 $i=6$ , 但刚好 $k=5$)，那么直接就可以给出答案

参考代码

这个代码是 深入浅出 提供的，由 Deepseek V4 Pro 和 笔者 改写而得

int ans = 0, k; // 记录答案，以及求第 k 小
void findkth(int a[], int l, int r) { // 引入数组的地址
    if(l == r) {
        ans = a[l]; // 区间长度为 1 时，记录答案
        return;
    }

    int i = l, j = r, flag = a[(l + r) / 2], tmp;
    do {
        while (a[i] < flag) i++; // 从左找比哨兵大的数
        while (a[j] > flag) j--; // 从右找比哨兵小的数
        if (i <= j) { // 交换
            tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++; j--;
        }
    } while (i <= j);

    if (k <= j) findkth(a, l, j); // 第 k 小的数字在左区间
    else if (i <= k) findkth(a, i, r); // 第 k 小的数字在右区间
    else findkth(a, j + 1, i - 1); // 第 k 小的数字既不在左区间，也不在右区间
}

尽管 此参考代码片段（快速选择） 相对于 快排（模板代码）类似，但是每次处理的区间长度期望下都会被减半，复杂度是线性的

快速排序 - 快速选择

这个概念是在书中没有的，是由 Deepseek V4 Pro 提出

它基于 快速排序 的分治思想，但并不是完整的排序算法，而是一种 选择算法 ——专门用来查找数组中第 $k$ 小（或第 $k$ 大）的元素

下面是一张表格，阐释了区别

所以，这种方法叫做 快速选择，也可以理解为"快速排序的简化版"或"基于快排分治的选择算法"

[collapse status="false" title="函数图像（可能有误）"]

这个部分由 Deepseek V4 Pro 与 豆包 提供，它们分别为这个部分 提供函数生成代码 和 提供函数图，在这里表示对他们最诚挚的感谢

但是目前看起来它们携手合作画出来的图有误，作为初二学生的笔者，无法验证这张图的真伪，所以这个问题抛给读者，抱歉

[/collapse]

4 排序的应用

这里提供了一些 排序 的拓展用法，在第二轮比赛时可能有用

【题目样本 4.1】P1059 [NOIP 2006 普及组] 明明的随机数

题目描述

https://www.luogu.com.cn/problem/P1059

给出 $N(N \lt 10^2)$ 个 $1 \sim 10^3$ 的数字，输出去重后剩余数字的个数以及去重排序后的序列

解法 1：计数排序

在拿到新的选票时发现投票箱中已经有这个选票了，就扔掉这张选票，保持每个票箱中最多只有一张票

最后将有票的票箱编号输出即可

这里要求先输出不同数字的个数，可以先枚举一遍票箱记录，输出剩余数字的个数，然后再枚举一遍票箱，输出序列

也可以创建一个新的数组，在枚举票箱的时候将有票的编号复制进新的数组中

解法 2：STL

当然也可以直接对这些数据进行排序，然后从小到大每个数字只输出一个

考虑数据规模，可以使用上面提到的所有排序方式

不过，这次介绍排序的 STL， 这样就不需要去亲自实现排序算法了

关于 STL，后面可能会出一个专门的专题，STL = Standard Template Library（标准模板库）

有了这个就不用自己手搓了

排序 STL 1：sort

分析

std::sort 被定义于 algorithm 头文件中，因此，你在使用前需要先导入这个头文件，为了方便笔者，笔者会尽可能地在后文省略较多的不影响理解的内容

sort 的基本用法如下

// 形式1：默认升序排序
sort(起始迭代器, 结束迭代器);

// 形式2：自定义比较规则
sort(起始迭代器, 结束迭代器, 比较函数/仿函数/Lambda); // 比较函数即 cmp 用的较多

一个例子，sort(a,a+n,cmp)，对 $a[]$ 数组从 $a[0]$ 到 $a[n-1]$ 进行排序，cmp 是指自定义排序函数，如果是将数组 $a[]$ 从小到大排序，那么这一项可以省略

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
int const MAXN = 1010;
int a[MAXN], ans[MAXN], n, cnt = 0, tmp = -1;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
    if (a[i] != tmp) ans[cnt++] = a[i]; /* 当前的和上一个不同才复制到新数组 */
    tmp = a[i];
    }
    cout << cnt << endl;
    for (int i = 0; i < cnt; i++) cout << ans[i] << ' ';
    return 0;
}

sort

这里，sort 的时间复杂度是 $O(n \log n)$

如果要对数组 $a[1]$ 到 $a[n]$ 排序，就要用 sort(a+1, a+n+1)

那么，如果要求从大到小排序，只需要定义一个名字是 cmp 的自定义比较函数即可，这个函数的输入是两个元素，如果第一个在第二个之前，则返回 true, 否则返回 false。代码如下：

bool cmp(int q,int h){ // q 前 h 后
    return q>h;
}

排序 STL 2：unique

分析

std::unqiue 同样被定义于 algorithm 头文件中

unique(a,a+n)：对 $a[]$ 数组从 $a[0]$ 到 $a[n-1]$ 进行去重，要求 $a[]$ 数组已经有序，返回去重后最后一个元素对应的指针

如果使用 unique, 就可以不用 ans 新数组了，可以直接获得去重后的数组和最终元素个数

参考代码

sort(a,a+n);
cnt=unique(a,a+n)-a; // 剩下的数总数
cout<<cnt<<"\n";
for(int i=0;i<cnt;i++) cout<<a[i]<<" ";

【题目样本 4.2】P1093 [NOIP 2007 普及组] 奖学金

题目描述

https://www.luogu.com.cn/problem/P1093

有 $n$（$n \le 300$）名学生的语文、数学、英语成绩，这些学生的学号依次是从 $1$ 到 $n$。需要对这些学生进行排序。如果总分相同，则语文分数高者名次靠前；如果语文成绩还相同，学号小者靠前。输出排名前 $5$ 的学生学号和总分

解法 1：STL

分析

定义一个 struct 结构体，命名为 student 存储学生各项信息，使用 sort 附带 cmp 比较函数进行排序，最后输出排序结果，下面是排序优先级

1. 总分，高者优先
2. 语文，高者优先
3. 学好，小者优先

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

int const MAXN = 310;
int n;

struct student {
    int id, chinese, total;
} a[MAXN];

int cmp(student a, student b) {
    if (a.total != b.total) return a.total > b.total;      // 总分先定胜负
    if (a.chinese != b.chinese) return a.chinese > b.chinese; // 然后比语文
    return a.id < b.id;                                    // 最后比学号
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int math, english;
        cin >> a[i].chinese >> math >> english;
        a[i].total = a[i].chinese + math + english;
        a[i].id = i + 1;
    }

    sort(a, a + n, cmp);

    for (int i = 0; i < 5; i++) {
        cout << a[i].id << " " << a[i].total << endl;
    }

    return 0;
}

解法 2：选择排序

分析

时间复杂度 $O(kn)$，此题 $k=5$，即 $O(n)$

解法 3：插入排序

分析

维护排名前 $5$ 数组作为比较对象（手牌）

时间复杂度 $O(n)$，运行效率不高

【题目样本 4.3】P1781 宇宙总统

题目描述

https://www.luogu.com.cn/problem/P1781

共有 ( n )（( n \le 20 )）个非凡拔尖的人竞选总统，现在票数已经统计完毕，请算出谁能够当上总统。第一行输出候选人编号，第二行输出选票数量。票数可能很大，最大会有 100 位

解法 1：计数排序

分析

由于本题只需要求出最大的那一个数字，所以用“打擂台”法

但是数字很大，没办法直接存下来（long long 也存不下）

但是需要高精度，不考虑单开一个话题

解法 2：结构体

分析

存进字符串。不过不能直接对这些字符串进行大小比较，因为字符串比较是比较字典序（第一位小的在前面，如果相同则比较第二位，以此类推），例如 $10000$ 小于 $1200$ 小于 $200$

得手搓 cmp

参考代码

struct node {
    string x;    // 票数
    int num;     // 候选人编号
} s[MAXN];

bool cmp(node a, node b) {
    if (a.x.length() != b.x.length()) {
        return a.x.length() > b.x.length(); // a 比 b 位数多时 a 在前面
    }
    return a.x > b.x; // 位数相同，但 a 字典序排列比 b 大
}

5 汇总

练习

笔者为读者提供了一些洛谷上没有的题目，供练习

• 计数排序
• 选择排序
• 冒泡排序
• 插入排序
• 快速排序

C++ 常用排序算法一览表

额外的，这里有一张特别大的表格，供读者查阅

[collapse status="false" title="C++ 常用排序算法一览表（无特点）"]

[/collapse]

C++ STL 中的排序一览表

同时，这里还有一张关于 STL 的表