[蓝桥杯] 挖矿（CC++双语版）

题目链接

          P10904 [蓝桥杯 2024 省 C] 挖矿 - 洛谷

题目理解

        我们可以将这道题中矿洞的位置理解成为一个坐标轴，以题目样例绘出坐标轴：

样例：

        输入的5为矿洞数量，4为可走的步数。第二行输入是5个矿洞的坐标。输出结果为在要求步数内最多可采集到的单位数量的矿石。

         我们下面来对样例进行分析：

        初始状态如下：

        初始位置为0，剩余步数为4。当坐标0有矿石时，不需要消耗步数，可直接获取矿石：

        我们向-1移动：

        此时若是向负轴移动，我们只能采到1个单位的矿石，正轴方向可以采到2个单位。于是我们向正轴方向进发：

        继续进发：

        继续：

 

解题思路

      ——(篇幅较长，大家也可以先看详细注释后的代码，遇到不懂的地方再看解题思路)——

   一、核心思路概述

        解决该挖矿问题的核心在于合理利用数轴上矿洞的分布信息以及移动距离限制，通过巧妙的统计和计算，找出在给定移动距离内能够挖掘到最多矿石的方法。主要步骤包括对矿洞坐标的分类统计、构建前缀和数组以快速计算区间矿洞数量，以及全面考虑不同移动策略下的矿石获取情况。

   二、具体步骤解析

    （一）输入数据处理

1. 读取矿洞数量 n 和最大移动距离 m，这两个参数将决定后续计算的范围和约束条件。

2. 依次读取 n 个矿洞在数轴上的坐标值，对于每个坐标值进行如下分类处理：

•         如果坐标值为 0，说明该矿洞位于小蓝的起始位置，直接将此类矿洞的计数变量 s 加 1。这些矿洞无需移动即可挖掘，对最终结果有直接贡献。
•         如果坐标值不为 0，且其绝对值小于等于 m，则根据坐标值的正负性分别处理。
•         若坐标值为负数，将其对应在负半轴的位置索引处的计数器（例如数组 l）加 1，用于统计负半轴上在移动距离范围内的矿洞数量。
•         若坐标值为正数，将其对应在正半轴的位置索引处的计数器（例如数组 r）加 1，用于统计正半轴上在移动距离范围内的矿洞数量。

  （二）构建前缀和数组

        1. 对于记录负半轴矿洞数量的数组 l，从索引 1 开始到 m，依次计算前缀和。即 l[i] = l[i - 1] + l[i]，这样 l[i] 就表示数轴负半轴上从 -1 到 -i 位置的矿洞总数。通过前缀和，我们可以在后续计算中快速得到负半轴某一区间内的矿洞数量。

        2. 同理，对于记录正半轴矿洞数量的数组 r，也从索引 1 开始到 m，计算前缀和 r[i] = r[i - 1] + r[i]，使得 r[i] 表示数轴正半轴上从 1 到 i 位置的矿洞总数。

  （三）计算最大矿石获取量

1. 初始假设：

•         首先假设最大矿石获取量 ans 为只在正半轴或只在负半轴移动时能够挖掘到的最大矿石数。即 ans = max(r[m], l[m])，这是一种简单的初步情况考虑，因为在某些情况下，仅在一个方向移动可能就能够获取最多的矿石。

2. 考虑混合移动策略：

•         通过循环遍历 i 从 1 到 m / 2（因为左右移动距离之和不能超过 m，所以 i 最大取到 m / 2），尝试不同的左右移动组合。 - 对于每一个 i 值，计算两种混合移动策略下能够挖掘到的矿石数：
•         先向右移动 i 单位距离，再向左移动 m - 2 * i 单位距离时，能够挖掘到的矿石数为 sr = r[i] + l[m - 2 * i]。这里 r[i] 表示向右移动 i 单位距离过程中挖掘到的正半轴矿洞数，l[m - 2 * i] 表示向左移动 m - 2 * i 单位距离过程中挖掘到的负半轴矿洞数。 - 先向左移动 i 单位距离，再向右移动 m - 2 * i 单位距离时，能够挖掘到的矿石数为 sl = l[i] + r[m - 2 * i]。这里 l[i] 表示向左移动 i 单位距离过程中挖掘到的负半轴矿洞数，r[m - 2 * i] 表示向右移动 m - 2 * i 单位距离过程中挖掘到的正半轴矿洞数。
•         每次计算出 sr 和 sl 后，更新最大矿石获取量 ans，即 ans = max(ans, sr, sl)，取当前的 ans、sr 和 sl 中的最大值作为新的 ans。

3. 加上起始点矿洞数量：

•         最后，将起始点（坐标为 0）的矿洞数量 s 加到 ans 中，因为这些矿洞在初始位置就可获取，无需移动。此时得到的 ans 即为在移动距离不超过 m 的前提下，小蓝最多能获得的矿石单位数量。 通过以上步骤，我们可以全面且高效地解决在给定条件下的挖矿问题，找到获取最多矿石的方案。

完整代码（详细注释）

        本文由于用到了std库中的一些函数，所以作者最开始采用了C++，C语言代码作者用ai转化并确保代码无误后给大家放在了下面。

    1.C++代码

#include <bits/stdc++.h>// 定义 solve 函数来解决挖矿问题
void solve() 
{int n, m;// 从标准输入读取矿洞数量 n 和最大移动距离 mstd::cin >> n >> m;// s 用于记录坐标为 0 的矿洞数量int s = 0;// 定义两个静态数组 l 和 r 来分别记录负半轴和正半轴矿洞的前缀和// 数组大小为 m + 1，初始化为 0int l[10000001] = {0};int r[10000001] = {0};// 遍历每个矿洞for (int i = 0; i < n; ++i) {int x;// 读取当前矿洞的坐标std::cin >> x;// 如果矿洞坐标的绝对值小于等于最大移动距离 m 且为负数//abs为绝对值函数if (std::abs(x) <= m && x < 0){// 对应负半轴的位置计数加 1l[-x]++;}// 如果矿洞坐标的绝对值小于等于最大移动距离 m 且为正数else if (std::abs(x) <= m && x > 0) {// 对应正半轴的位置计数加 1r[x]++;}// 如果矿洞坐标为 0else if (x == 0) {// 坐标为 0 的矿洞数量加 1s++;}}// 计算负半轴矿洞的前缀和for (int i = 1; i <= m; ++i){l[i] += l[i - 1];}// 计算正半轴矿洞的前缀和for (int i = 1; i <= m; ++i) {r[i] += r[i - 1];}// 先假设最大矿石数为只走正半轴或只走负半轴能挖到的最大矿石数int ans = std::max(r[m], l[m]);// 尝试不同的左右移动组合，i 表示先向一个方向移动的距离for (int i = 1; i <= m / 2; ++i) {// 先向右移动 i 的距离，再向左移动 m - i * 2 的距离能挖到的矿石数int sr = r[i] + l[m - i * 2];// 先向左移动 i 的距离，再向右移动 m - i * 2 的距离能挖到的矿石数int sl = l[i] + r[m - i * 2];// 更新最大矿石数ans = std::max({ans, sr, sl});}// 加上坐标为 0 的矿洞数量ans += s;// 输出最大能获得的矿石数std::cout << ans << '\n';
}int main() 
{solve();return 0;
}

     2.C语言代码 

#include <stdio.h>
#include <math.h>#define MAX_M 10000001// 定义 solve 函数来解决挖矿问题
void solve() {int n, m;// 从标准输入读取矿洞数量 n 和最大移动距离 mscanf("%d %d", &n, &m);// s 用于记录坐标为 0 的矿洞数量int s = 0;// 定义两个静态数组 l 和 r 来分别记录负半轴和正半轴矿洞的前缀和// 数组大小为 MAX_M，初始化为 0int l[MAX_M] = {0};int r[MAX_M] = {0};// 遍历每个矿洞for (int i = 0; i < n; ++i) {int x;// 读取当前矿洞的坐标scanf("%d", &x);// 如果矿洞坐标的绝对值小于等于最大移动距离 m 且为负数if (abs(x) <= m && x < 0) {// 对应负半轴的位置计数加 1l[-x]++;}// 如果矿洞坐标的绝对值小于等于最大移动距离 m 且为正数else if (abs(x) <= m && x > 0) {// 对应正半轴的位置计数加 1r[x]++;}// 如果矿洞坐标为 0else if (x == 0) {// 坐标为 0 的矿洞数量加 1s++;}}// 计算负半轴矿洞的前缀和for (int i = 1; i <= m; ++i) {l[i] += l[i - 1];}// 计算正半轴矿洞的前缀和for (int i = 1; i <= m; ++i) {r[i] += r[i - 1];}// 先假设最大矿石数为只走正半轴或只走负半轴能挖到的最大矿石数int ans = (r[m] > l[m]) ? r[m] : l[m];// 尝试不同的左右移动组合，i 表示先向一个方向移动的距离for (int i = 1; i <= m / 2; ++i) {// 先向右移动 i 的距离，再向左移动 m - i * 2 的距离能挖到的矿石数int sr = r[i] + l[m - i * 2];// 先向左移动 i 的距离，再向右移动 m - i * 2 的距离能挖到的矿石数int sl = l[i] + r[m - i * 2];// 更新最大矿石数if (sr > ans) ans = sr;if (sl > ans) ans = sl;}// 加上坐标为 0 的矿洞数量ans += s;// 输出最大能获得的矿石数printf("%d\n", ans);
}int main() {solve();return 0;
}

       AC拿下！

疑难解答 

    1.max函数的运用

        用于比较出几个数中最大的数字，大家可以简单理解为两个数比较就不需要大括号，如果三个及以上的话需要大括号。

• 两个参数比较：当比较两个值时，使用 std::max(a, b) 形式，这里 a 和 b 是要比较的对象，不需要大括号。比如 int num1 = 5, num2 = 3; int maxNum = std::max(num1, num2); 。
• 三个及以上参数比较：对于三个或更多值，常使用接收初始化列表形式的重载，即 std::max({val1, val2, val3,...}) ，需要用大括号把这些值组成初始化列表传递给函数。像 int num1 = 1, num2 = 2, num3 = 3; int maxNum = std::max({num1, num2, num3}); 。

---

———（如有问题，欢迎评论区提问）———