剑指信奥 | C 语言之信奥试题详解（三）
前言
今天是我们 C 语言详解信奥试题的第三天，我们稍微提升一下难度。
解决难题的过程需要更多一些的思考，解决了难题的收获也是非同一般，挑战一下自我吧！
No. 1 分配任务 🌟
题目
在社会实践活动中有三项任务分别是：种树、采茶、送水。
依据小组人数及男生、女生人数决定小组的接受任务：
人数小于 10 人的小组负责送水（输出 water），人数大于等于 10 人且男生多于女生的小组负责种树（输出 tree），人数大于等于 10 人且男生不多于女生的小组负责采茶（输出 tea）。
输入小组男生人数、女生人数，输出小组接受的任务。
输入格式一行两个空格隔开的数，表示小组中男生和女生的人数。
输出格式输出对应的任务。
样例输入5 3
样例输出water
题解
题目分析这道题有很多的文字描述信息，在实际的信奥试题中，这样的题型非常多。
我们需要做的是快速的提取题目的主要信息，从本质上判断题目所需要使用的算法。
不难分析，这道题是根据 3 个数值决定 3 个输出：
男生人数 / 女生人数 / 男生人数 + 女生人数
water / tree / tea
而其中输入与输出的规则在题目中已经说明的很清楚了，不难看出，这道题考察的多分枝选择结构。
注意事项- 注意数值比较的边界
- 输入男女生人数
- 根据题意判断并输出
参考代码
#include <stdio.h>
int main() {
int m, f; // m 是男生数，f 是女生数
scanf("%d %d", &m, &f);
if (m + f < 10) {
printf("water");
} else if (m > f) {
printf("tree");
} else {
printf("tea");
}
return 0;
}
No. 2 级数求和 🌟🌟
题目
已知：Sn = 1 + 1/2 + 1/3 + … + 1/n。
显然对于任意一个整数 k，当 n 足够大的时候，Sn > k。
现给出一个整数 k，要求计算出一个最小的 n，使得 Sn > k。
输入格式一个正整数 k。
输出格式一个正整数 n。
样例输入1
样例输出2
数据范围对于 100% 的数据，1 ≤ k ≤ 15。
题解
题目分析Sn 是一个级数表达式，或许有同学会说，我没有学过级数，这道题怎么做？
其实在这道题中，并不需要了解什么是级数，透过这层表面信息，我们发现级数表达式是一个累加的过程，只要 n 足够大，Sn 的确可以大于任意的数 k。
所以这道题就转为一个求级数和的问题，当 Sn 第一次超过给定的 k 时，输出这时的 n，即为所求结果。
注意事项- 表达式涉及到除法并需要精确的结果，数据类型应为浮点型
- 使用 while 做无限循环，第一次满足条件时使用 break 终止循环
- 输入 k 的值
- 在循环中求级数
- 每次做大小判断
- Sn > k 时输出 n
#include <stdio.h>
int main() {
int k;
double s = 0; // 级数
double n = 1;
scanf("%d", &k);
while (1) { // 无限循环
s += 1.0 / n;
if (s > k) {
break; // 终止循环
}
n++;
}
printf("%.0lf", n);
return 0;
}
No. 3 校门外的树 🌟🌟🌟
题目
某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 L 的位置；数轴上的每个整数点，即 0, 1, 2, …, L，都种有一棵树。
由于马路上有一些区域要用来建地铁，这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。
现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式第一行有 2 个整数 L（1 ≤ L ≤ 10000） 和 M（1 ≤ M ≤ 100），L 代表马路的长度，M 代表区域的数目，L 和 M 之间用一个空格隔开。
接下来的 M 行每行包含 2 个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出格式1 个整数，表示马路上剩余的树的数目。
样例输入500 3
150 300
100 200
470 471
样例输出298
数据范围对于 20% 的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。
题解
题目分析这道题目的文字信息又多了一些，还记得吗，我们要快速的分析并提取题目的本质内容。
首先，我们知道 L 是一条线段，单位长度为 1，包括端点在内共有 L + 1 个点。
现在要去掉这条线段上的若干个点，去掉的过程根据这条线段上的多个小的线段来决定。
至于小线段是多少个并不确定，而且小线段之间有的没重合，有的有重合，都不确定...
感觉是不是一团乱？
看起来，这是一个复杂的问题，我们面对这类问题要采用一种 分治 的方法。
分治就是把大的问题分解为小的问题，或复杂的问题化简为容易的问题。
然后我们来处理这些小的问题或容易的问题，难度一下就降低了。
当这些问题解决后，我们再合并一下，原问题也就相应的解决了：
分而治之
那这道题怎么化简呢？
我们发现这道题的复杂之处在于 M 个线段数量和起止点都不确定，那我们就简化一下，如果只有一个线段，这道题应该怎么做？
我们发现，这样简单多了：
我们可以把 L 线段所有的点放进一个 L + 1 的数组，为数组每个元素赋初始值为 1，表示有树。
然后再遍历小线段，把涉及到的元素赋值为 0，最后统计剩下的 1 就可以了。
这样，我们一个简单的问题就解决了。
那我们来合并一下，如果有 M 个线段且长短不一甚至还有可能重合呢？
一样的过程，每次把涉及到的元素赋值为 1 就可以了，这是一个 M 次的循环。
至于重不重合我们已经不必关心了。
这样，我们整个的问题就解决了。
注意事项- 注意线段的边界问题
- 定义 L + 1 数组，赋初始值 1
- 循环 M 次，为部分元素赋 0
- 统计剩余 1 元素的数量
#include <stdio.h>
int main() {
int l, m;
scanf("%d %d", &l, &m);
intarray[l + 1]; // L + 1 数组
// 赋初始值为 1
for (int i = 0; i < l + 1; i++) {
array[i] = 1;
}
// M 次循环
for (int i = 0; i < m; i++) {
int start, end;
scanf("%d %d", &start, &end);
for (int j = start; j < end + 1; j++) {
array[j] = 0; // 赋 0
}
}
int left = 0;
// 统计剩余 1 元素的数量
for (int i = 0; i < l + 1; i++) {
if (array[i] == 1) {
left++;
}
}
printf("%d", left);
return 0;
}