[数据结构与算法]算法竞赛：输入

专栏：算法竞赛

上一篇：算法竞赛：Online Judge介绍

下一篇：

一、 数据的读取方式

（一） 自行处理输入

??目前在大部分的 OJ 网站中，用户需要编写一个完整的程序。此时需要用户在提交的代码中自行读取输入。

??程序要读取的数据被保存在文件中，内容以文本的形式给出，用户可以通过标准输入输出来进行读取。

??如果数据是保存在文件中的话， 为什么不需要用文件操作就可以直接用标准输入读取呢？标准输入不是从终端读取的吗？

• 这是因为使用了输入重定向，将标准输入重定向到文件，所以使用标准输入将会从文件中读取，在下文中会讲解。

如上图所示的输入格式，C 只需要调用如下代码便可读取

int a, b;
scanf("%d %d", &a, &b);

如果使用C++，则为

int a, b;
std::cin >> a >> b;

头文件包含

（二）从函数参数中获取

LeetCode 题目：两数之和

??一小部分 OJ 网站(如 LeetCode )已经做好了整个程序的框架，完成了数据的读取，并将数据传到函数参数中。用户需要按题目要求补充函数或类的内容。

??用户需要选用算法，实现函数功能，从函数参数中获取数据，计算出正确值并返回。

??如下所示，是 LeetCode 中的 两数之和 题目。

??在代码编辑区域中，可以看到默认生成了个twoSum() 函数。用户需要按题目要求，在函数中实现相应功能，并将结果通过 函数返回值 或 函数参数 返回。

二、变量及其输入

??这里讲解在需要自行读取输入的情况。

（一） 数据的输入：字符流

??题目给出的数据是 以字符的形式存储在文件中，程序在读取数据的时候，读取到的也是一个个字符，也就是说，数据是以字符流的形式被程序读取。

例如，对于 输入样例：20 30 来说：

• 程序读取的内容相当于是字符序列： "20 30"
• 保存的内容并不是理解上的数字，直接就对应整型值 0x00000014 0x0000001E，而是字符序列 "20 30" 中字符按顺序所对应的 ASCII码： 0x32 0x30 0x20 0x33 0x30，可以使用 getchar() 函数来进行验证。

??既然数据是以字符流的形式被读取，那么读取到的应该是字符，为什么像 std::cin 或能 scanf() 直接读取数值存储到变量中呢？

----------------------------
//包含头文件
#include <stdio.h>
#include <iostream>
----------------------------

int a, b;
//C语言 标准输入
scanf("%d %d", &a, &b);

//C++ 标准输入
std::cin >> a >> b;

??这是因为标准输入对从字符流中读取到的内容进行了解析，根据变量类型将字符串转成对应的数值，并存储到变量中。

??例如：对于字符串 "1234"，如果想要解析成数值：
??当以十进制数解析时，只需要在每接收到一个字符时，原累计值 乘以基数10 并加上字符对应的数值(与字符'0' 的ASCII码差值)即可，结果为 $1234_{(10)}$ 。$$((1?10+2)?10+3)?10+4=1234$$??当以十六进制数解析时，只需改成乘以基数16即可，结果为 $1234_{(16)}$ ，即十进制的 $4660$。$$((1?16+2)?16+3)?16+4=4660$$

??总之，在算法竞赛中，数据的输入是以字符流的形式，而不是以字节流的形式，数值读取是对字符序列进行解析的结果。如果字符序列中内容与数据类型的格式不符，可能就会造成读取错误，与期望的结果相悖。

（二） 基本数据类型

?? C++ 的基本数据类型有以下几种，数据类型所占的字节大小与平台有关。下面列出的各数据类型大小是目前在32位和64位平台上数据类型的通常实现。

对于各平台上数据类型 实际所占的字节数，建议使用 sizeof 关键字来确定： sizeof(type)

1. 整数类型

各整数类型的范围被定义在 <limits.h> 头文件中。

??C++标准实际上只确保各 int 相关类型的最小长度，而并没有确切地规定各类型的长度。所以下面类型所占的字节大小只是各32位, 64位平台的通常实现，在算法竞赛中基本按照下表来认定。

??鉴于上面整数类型位数的不确定性，C99 和 C++11 标准还在<stdint.h>头文件中另外定义了一些确保位数的整数类型：

2. 浮点类型

浮点类型的数值范围定义在 <float.h> 头文件中。

??对于浮点类型的来说，float型尾数有24位，可以精确表示二进制24位以内的整数，当有效数字超过这个值时，会因为位数不足而造成误差，低位将被近似舍去。
??对于十进制小数来说，大部分是无法用二进制小数精确表示的，所以就会有一个误差，通过增加浮点数的位数能提高精度，减小误差。
??下面则是常用的两个浮点类型： float 和 double。

?? long double 是在 C99 引入的，且标准里并没有规定 long double 的位数，只要求不小于double， 如同int 和 long 的关系。在 MSVC 中，long double 和 double 是一样的。

3. 布尔型

??布尔型只有 false 和 true 两个值，用于逻辑判断。

（三） 变量类型的选取

??数值小于 $10^8$ 的整数可以用 int 型读取，当数值大于 $10^8$ 时，考虑使用 long long 或者 unsigned int，如果数值非常大，无法用基本数据类型来存储，则考虑使用 大数运算。

??浮点类型通常使用 double ，如果精度要求不高则可以使用 float， 当需要更高精度时可以使用 long double。

??同时，double 类型的精度有52位，比 int 高， int 可以转换成 double 而不丢失精度。float 则不可以， float 的精度只有24位，比 int 小，int 数值过大时容易丢失精度。

??字符型数据可以使用 char 型，通常输入的是一个字符串，此时使用 char 型数组存储。

（四） 变量的输入

cppfeference 中 scanf()说明

??当使用 C 中的 scanf() 来进行输入时，需要使用格式说明符来说明变量的类型，并传入变量的地址。

??对于 C++ 中的 std::cin ，由于本身是面向对象的，所以可以自动根据变量类型进行解析。当设定输入的值为十六进制，十进制和八进制时，可以使用I/O操纵符。

cppreference : I/O操纵符

如：std::hex, std::dec, std::oct，示例如下：

int a, b, c;
//第1个数为 十六进制格式，第2个为 八进制格式, 第3个数为 十进制
std::cin >> std::hex >> a >> std::oct >> b >> std::dec >> c;

1. scanf()的返回值

??scanf() 函数的返回值是正确读取并赋值的变量个数。特别的，当因读取到文件末尾而无法读取到变量时，不再返回0，而是返回 EOF(-1)。

int a, b;

while (scanf("%d %d", &a, &b) != 2) {
}

2. C++ cin 转bool

??C++中的 std::cin 转成bool 时，如果读取时出现错误，就会返回 false ，如读取到文件末尾、输入与变量类型不匹配等。可以借此来判断是否读取到文件末尾。

当读取出现错误后，后续读取将无效，需要做一些清除错误的操作才能继续读取。

int a, b;

while (std::cin >> a >> b) {
}

三、输入格式

??题目输入的数据通常以空格和换行隔开，这些数据有着不同的排列格式，需要按照不同的方式去读取。

在输入中，规范的格式是：

• 行内的数据用一个空格隔开
• 每一行末尾都有一个换行符

（一） 输入数据个数固定

??对于有着固定数量的输入：

输入样例

$1234$

(1) 可以定义同样数量的变量或数组，在格式字符串中按顺序指定。

int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);

(2) 定义同样长度的数组，根据数据个数循环读取

//定义数组
const int N = 4;
int a[4];

//循环读取
for (int i = 0; i < N; i++) {
	scanf("%d", &a[i]);
}

（二） 指定行内数据个数

??输入首先给出 数据个数 $n$， 然后给出 $n$ 个数据：$a_0,a_1,a_2,a_3,?,a_{n?1}$。

输入样例

$6$
$20300129954$

(1) 如果题目中给出的 $n$ 的范围较小，假定不大于 $N$，则可以先配一个可以容纳N个元素的数组。

1. 定义变量 n 和数组 a[N]
2. 先读取 $n$ 到变量 n，然后循环 $n$ 次将 $n$ 个输入读取到数组a[]中。

int a[N];

//读取 n
int n;
scanf("%d", &n);

//读取n个输入到数组中
for (int i = 0; i < n; i++) {
	scanf("%d", &a[i]);
} 

(2) 如果题目中给出的 $n$ 的范围较大则可以使用动态分配。

1. 先定义变量 n 并读取数值 $n$ 。
2. 动态分配一个长度为 $n$ 的数组，并循环 $n$ 次读取输入到数组中。
3. 使用结束后销毁数组。

int n;
scanf("%d", &n);

//动态分配
int* a = new int[n];

//读取n个输入到数组中
for (int i = 0; i < n; i++) {
	scanf("%d", &a[i]);
}

...

//使用结束后销毁数组
delete[] a;

（三） 行内数据数量任意

??输入中并未给出一行的输入数量，规定了最大长度或没有规定。

输入样例

$20300129954$

这种形式的数据一般以两种方式处理：

• 一种是直接读取，检测到换行符则停止；
• 另一种是先读取一行内容，把字符串存储到字符数组中，然后再对字符串读取(或者将字符串按空格分割后再读取）。

1. 直接读取，检测到换行符'\n'后停止

??数据之后紧邻着的是一个 空格 或者一个 换行符'\n'，标准输入在读取数值时会自动跳过空格。在读取时可以将数据后的一个字符读出，当检测到是换行符时停止。

这种做法要求输入格式规范，如果换行符 之前存在空格，检测将失效。

• 如果题目规定了最大长度，并且最大长度较小，可以直接分配一个大小为 $maxlen$ 的数组。
• 如果数据量范围较大且最大长度较大，则可以采用动态分配方式，当数组长度达到最大容量时使用 realloc() 重新分配一个更大的数组。
• 或者使用 C++标准库 中可以自行增长的 vector。

① 直接开辟可容纳最大数据长度的数组

int a[128];
int length = 0;

while (true) {
	//赋初值，防止被ch没读取成功的情况干扰
	char ch = '\0';
	int readVarNum;

	//读取数值到变量中，并将数据后的一个字符赋给ch，用于检测是否换行
	readVarNum = scanf("%d%c", &a[length], &ch);

	//判断变量是否读取成功
	if (readVarNum >= 1) {
		length++;
	}

	//读取不到足够的变量，或者间隔符非空格则停止读取读取
	if ((readVarNum != 2) || (ch != ' '))
		break;
}

② 动态分配，自动扩充

#include <stdio.h>
#include <stdlib.h>

int maxLen = 8;
int* a = (int*)malloc(maxLen * sizeof(int));
int length = 0;

while (true) {
	//赋初值，防止被ch没读取成功的情况干扰
	char ch = '\0';
	int readVarNum;
	int temp;

	//读取数值到变量中，并将数据后的一个字符赋给ch，用于检测是否换行
	readVarNum = scanf("%x%c", &temp, &ch);

	//判断变量是否读取成功
	if (readVarNum >= 1) {
		a[length++] = temp;

		//这里扩充分配的内存大小
		//如果使用vector<int>的话，直接push_back()即可，内部会自动扩充
		//这里则使用普通的数组作为示例
		if (length >= maxLen) {
			maxLen = 2 * maxLen;
			int* a = (int *) realloc(a, maxLen * sizeof(int));
		}
	}

	//读取不到足够的变量，或者间隔符非空格则停止读取读取
	if ((readVarNum != 2) || (ch != ' '))
		break;
}

② 使用Vector自动管理

std::vector<int> vec;

while (true) {
	//赋初值，防止被ch没读取成功的情况干扰
	char ch = '\0';
	int readVarNum;
	int inData;
	
	//读取数值到变量中，并将数据后的一个字符赋给ch，用于检测是否换行
	readVarNum = scanf("%d%c", &inData, &ch);
	vec.push_back(inData);

	//读取不到足够的变量，或者间隔符非空格则停止读取读取
	if ((readVarNum != 2) || (ch != ' '))
		break;
}

2. 先读取一行，再对字符串进行处理

??在读取一整行后，可以使用相关函数对字符串进行分割或者直接读取。

2.1 读取一整行

??读取一整行可以使用 C 中的 fgets()， 或者C++中的std::cin.getline() 或 getline() 函数。
??如果使用 char 数组来保存字符串，那么需要提前分配好内存，最好在正常情况下可以容纳一整行的字符，否则就要写比较多的相关处理代码。

C式写法：

#include <stdio.h>

char str[1024];
if (fgets(str, 1024, stdin) == NULL) {
	读取失败
}

??可以通过检测字符串 str 的最后一个字符是否为 '\n'来判断是否读取完了一整行。如果返回值ptrBuff为空指针，说明读取失败，这种情况下 str 的内容不会被改变。

C++式写法1：

#include <string>
#inclde <iostream>

std::string line;
if (!std::getline(std::cin, line)) {
	读取失败
}

C++式写法2：

#include <string>
#inclde <iostream>

char str[1024];
if (!std::cin.getline(str, 1024)) {
	读取失败
}

2.2 从字符串中读取数据

2.2.1 stringstream

??C++可以使用 stringstream 由 string 创建一个流，然后从流中读取数据到变量中。

#include <string>
#include <sstream>
#include <vector>

//假设line存储了一整行的字符
std::string line; 

std::stringstream strstream(line);

//此时stringstream可以和cin类似的操作
int x;
vector<int> vec;

while (strstream >> x) {
	vec.push_back(x);
}

2.2.2 strtok() 分割字符串

??C中的 strtok() 函数可以对函数进行分割，函数原型如下，str 为要进行分割的字符串 (需要允许被修改，不能是const)，delimiter是由分割字符串的分隔符组成的字符串 (一个或多个)。

#include <string.h>
char* strtok( char* str, const char* delimiter);

??如果字符串的分隔符之间没有其它字符，即空字符串，会被跳过，不会返回。如"1, , , , 2" 用 " ,"(空格和逗号)分割时，只会返回子串 "1" 和子串 "2"。

先看一个简略的示例：

//传入要分割的字符串，以及分隔符，得到分割出的第一个子串
char* subStr = strtok(str, " ");

//循环直到返回NULL
while (subStr != NULL) {
	//传入NULL，继续分割出下一个子串
	subStr = strtok(NULL, " ");
}

下面是使用方法：

1. 第一次调用传入要分割的字符串 str，字符串内容需要允许被修改，因为strtok()会将字符串中的分隔符改成'\0'。返回的则是分割后的第一个子串。

char* subStr = strtok(str, " ,;");

2. 后续调用，字符串传入NULL，因为内部已经保存有之前字符串的地址了，传入NULL表示继续分割。

char* subStr = strtok(NULL, " ,;");

3. 当返回的子串 subStr == NULL时，表示已经分割完毕。

??因为数据之间是用空格分隔的，所以分隔符使用" "就好，如果 空格 、 逗号, 和 分号; 都有，那么分隔符可以加三个字符 " ,;"。
??下面是实际的操作，假设数据已经被读入 str[] 中。

#include <string.h>

char str[1024];
...//读取一整行数据

int a[128];
int length = 0;

//第一次分隔，传入字符串str和分隔符集合
char* subStr = strtok(str, " ");

//分割出的字符不为`NULL`则说明没有分割完成
while (subStr != NULL) {
	//在保证输入的数据无误的情况下，可以直接从子串读
	//否则还得通过sscanf()的返回值判断一下是否读取成功
	sscanf(subStr, "%d", &a[length++]);
	
	//继续分割
	subStr = strtok(NULL, " ");
}

??经过 strtok() 分割后，字符串 str 中每个子串后面的第一个分隔符会变成'\0'，如果分隔符是连续的，这些连续的分隔符中只有第一个会被修改成'\0'。

如： "1, ,2,,,3" 被 " ,"分割后会变成 "1\0 ,2\0,,3"

2.2.3 利用字符查找

?还有其它一些通过字符查找操作来确定数据位置，从而进行读取。

四、C++ iostream提速

??C++ 中 的 iostream 在实际使用时会比 C 中的 stdio 慢一些，这在有些需要大量读写且时间限制得很紧的题目中可能会成为瓶颈。

??在需要提速时，可以使用以下代码进行提速，即取消 iostream 与 studio的同步，以及解除输入输出流的关联。

#include <iostream>

std::ios::sync_with_stdio(false);
std::cin.tie(NULL);

能提速多少？
??这和编译器有关，简单地在MSVC 和 GCC上进行100000个数据的读取测试，得到粗略的时间数据：

??可以看到，GCC上 cin 经过两个步骤后，提速十分明显，速度甚至比 scanf() 快得多，而在MSVC上，则达不到 scanf()的速度。

（一） 取消iostream与stdio的同步

??C++ 中 的 iostream 为了确保能和 C 中的 stdio在同一文件操作时按顺序进行，而进行了一些额外的同步操作，这些操作会对性能造成一些影响，可以使用 std::ios::sync_with_stdio(false)取消同步。
??取消同步后，性能可能会得到提升，但之后不应再与 stdio 混用，否则读写顺序上不能保证。

#include <iostream>

//取消iostream对stdio的同步
std::ios::sync_with_stdio(false);

（二） 解除输入输出流的关联

??C++ 中的 输入流 std::cin 默认是关联到 输出流 std::cout 的，任何试图从输入流 读取数据的操作都会先刷新关联的 输出流，这样输出流的缓冲区就会在输入前得到刷新。

??关联输入输出流意味着所有输出(包括用户提示等)都会在输入前被打印出来，而不会有在进行输入时之前调用的输出没有得到显示的情况发生。

??可以通过使用 cin.tie()解除输入输出流的关联来提升性能。

#include <iostream>

//解除cin 与 cout的关联
std::cin.tie(NULL);

??可以使用std::cin.tie() 重新关联。

#include <iostream>

//关联 cin 与 cout
std::cin.tie(&std::cout);

专栏：算法竞赛

上一篇：算法竞赛：Online Judge介绍

下一篇：

2022深度学习开发者峰会

5月20日13:00让我们相聚云端，共襄盛会！