题解 B2049 【最大数输出】

· · 题解

我们不妨把题目的意思转变一下：给定一个长度为 3 个元素的数列，求这个数列的最大值。

显然，我们可以直接使用 \text{STL} 内部自带的 max 函数进行求解，核心代码如下：

cout << max(a, max(b, c)) << endl;

注意：需要添加头文件 #include <algorithm> 或 #include <bits/stdc++.h> 才能使用。

还有另外一种比较常见的做法：将数列先从小到大进行排序，输出最大的元素。排序的方法也可以使用 \text{STL} 中的 sort 函数进行求解，功能是利用快速排序将数组进行排序，时间复杂度 T(n)=\mathcal{O}(n \operatorname{log} n)。

时间复杂度一般用符号 \mathcal{O} 表示。一个算法里语句的执行次数可以用一个式子表示，取这个式子的最高次项且忽略系数表示该算法的时间复杂度。例如，一个程序的语句执行次数为 2n+3n^2+9+8n，则该算法的时间复杂度为 \mathcal{O}(n^2)。

核心代码：

sort(a + 1, a + 4);
cout << a[3] << endl;

解释：a 为题面中给出的数列，在代码中就是数组。在访问数组时，直接访问数组名可以访问到数组第一个元素的地址，由于我的代码习惯是从 1 开始使用下标，所以需要将地址 +1。原本的 a, a + 3 就变为了 a + 1, a + 4，此处的 4 即为 3+1 的结果。

注意：此处的 sort 函数仍然需要添加上述的两个头文件。

对于快速排序内部更详细的实现流程，可以参考 P1177 【模板】快速排序 中其他同学的优秀题解。

对于时间复杂度的详细解释，可以查看作者的 CSP初赛知识点梳理 的「复杂度」部分