问题描述

小蓝正在数轴上挖矿，数轴上一共有 nn 个矿洞，第 ii 个矿洞的坐标为 aiai​ 。 小蓝从 0 出发，每次可以向左或向右移动 11 的距离，当路过一个矿洞时，就会进行挖矿作业，获得 11 单位矿石，但一个矿洞不能被多次挖掘。小蓝想知道在移动距离不超过 mm 的前提下，最多能获得多少单位矿石?

输入格式

输入的第一行包含两个正整数 n,mn,m，用一个空格分隔。

第二行包含 nn 个整数 a1,a2,⋯,ana1​,a2​,⋯,an​，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

5 4
0 -3 -1 1 2

样例输出

4

样例说明

路径：0→−1→0→1→20→−1→0→1→2，可以对 0,−1,1,20,−1,1,2 四个矿洞挖掘并获得最多 4 块矿石。

评测用例规模与约定

对于 20%20% 的评测用例，1≤n≤1031≤n≤103；

对于所有评测用例，1≤n≤105,−106≤ai≤106,1≤m≤2×1061≤n≤105,−106≤ai​≤106,1≤m≤2×106 。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	3s	512M
Python3	10s	512M
PyPy3	3s	512M
Go	5s	512M
JavaScript	5s	512M

总通过次数: 4639  |  总提交次数: 6352  |  通过率: 73%

难度: 中等   标签: 前缀和, 枚举, 省赛, 2024

算法思路

本问题要求在移动距离不超过 m 的前提下，在数轴上挖掘最多矿洞。核心思路是通过贪心策略和前缀和优化，高效计算最多可挖掘的矿洞数量。移动路径最多折返一次（先左后右或先右后左），因为多次折返会浪费步数。

1. ​​问题分析​​：

   • 矿洞分布在数轴上，起点为0。
   • 每次移动1单位距离，移动总距离不超过 m。
   • 路径分为两类：
     • ​​不折返​​：只向左或只向右移动。
     • ​​折返一次​​：先向左（右）走 x 步，再折返向右（左）走剩余步数 m - 2x。

2. ​​关键策略​​：

   • ​​分类统计矿洞​​：
     • 0点矿洞直接计数。
     • 正半轴和负半轴的矿洞分别存入数组 r 和 l（只记录绝对值 ≤ m 的矿洞）。
   • ​​前缀和优化​​：
     • 对 l 和 r 数组计算前缀和，快速获取任意区间内的矿洞数量。
   • ​​枚举折返点​​：
     • 枚举折返前的移动步数 x（0 ≤ x ≤ m/2），计算两种折返路径的矿洞数。

3. ​​数学表示​​：

   • 折返路径矿洞数：
     • 先左后右：l[x] + r[m - 2x]
     • 先右后左：r[x] + l[m - 2x]
   • 总矿洞数 = max(折返路径矿洞数) + 0点矿洞数。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    int zero_count = 0;
    vector<int> l(m + 1, 0); // 负半轴矿洞计数（l[i]表示坐标 -i 的矿洞数）
    vector<int> r(m + 1, 0); // 正半轴矿洞计数（r[i]表示坐标 i 的矿洞数）

    // 分类统计矿洞
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] == 0) {
            zero_count++;
        } else if (a[i] > 0 && a[i] <= m) {
            r[a[i]]++;
        } else if (a[i] < 0 && -a[i] <= m) {
            l[-a[i]]++;
        }
    }

    // 构建前缀和
    for (int i = 1; i <= m; ++i) {
        l[i] += l[i - 1];
        r[i] += r[i - 1];
    }

    int ans = 0;
    // 枚举折返点
    for (int x = 0; x <= m / 2; ++x) {
        int rem = m - 2 * x; // 剩余步数
        if (rem < 0) break;

        // 先左后右：挖负半轴[1, x] + 正半轴[1, rem]
        int case1 = l[x] + r[min(rem, m)];
        // 先右后左：挖正半轴[1, x] + 负半轴[1, rem]
        int case2 = r[x] + l[min(rem, m)];
        ans = max({ans, case1, case2});
    }

    ans += zero_count; // 加上0点矿洞
    cout << ans << endl;
    return 0;
}

算法演示

实例验证

​​样例输入​​：5 4\n0 -3 -1 1 2
​​处理过程​​：

1. ​​分类统计​​：
   • 0点：zero_count = 1
   • 负半轴：l[1] = 1（坐标-1），l[3] = 1（坐标-3）
   • 正半轴：r[1] = 1（坐标1），r[2] = 1（坐标2）
2. ​​前缀和​​：
   • l = [0, 1, 1, 2, 2]（负半轴≤i的矿洞数）
   • r = [0, 1, 2, 2, 2]（正半轴≤i的矿洞数）
3. ​​枚举折返点​​：
   • x=0：rem=4 → case1 = 0 + 2 = 2，case2 = 0 + 2 = 2
   • x=1：rem=2 → case1 = 1 + 2 = 3，case2 = 1 + 1 = 2
   • x=2：rem=0 → case1 = 1 + 0 = 1，case2 = 2 + 0 = 2
4. ​​结果​​：max(2, 3, 2) = 3 → 3 + 1 = 4（符合样例输出）

测试点分析

1. ​​边界情况​​：
   • m=0：只能挖0点矿洞（如输入 2 0\n0 -1 → 输出 1）。
   • 无0点矿洞：如输入 3 3\n1 -1 2 → 输出 3。
2. ​​极端数据​​：
   • 所有矿洞在0点：输入 10^5 0（0点矿洞数 = n）。
   • 矿洞集中在一侧：如全部在正半轴，验证 r[m] 计算正确。
3. ​​性能测试​​：
   • n=10^5, m=2×10^6：确保在1秒内完成（前缀和+枚举折返点，时间复杂度 O(n + m)）。

优化建议

1. ​​空间优化​​：
   • 若 m 极大（接近 2×10^6），使用 vector 而非静态数组，避免栈溢出。
2. ​​时间优化​​：
   • 输入优化：ios::sync_with_stdio(false); cin.tie(nullptr);。
   • 循环内联：编译器自动优化简单循环（如前缀和计算）。
3. ​​逻辑优化​​：
   • 折返枚举范围 x ≤ m/2，避免无效计算。
   • 剩余步数 rem 超出 m 时取 m（min(rem, m)）。

注意事项

1. ​​矿洞去重​​：
   • 同一坐标可能有多个矿洞，需累加计数（如输入 2 3\n1 1 → r[1] = 2）。
2. ​​坐标范围​​：
   • 仅处理绝对值 ≤ m 的矿洞（超范围无法到达）。
3. ​​前缀和边界​​：
   • 数组下标从0开始，l[0] 和 r[0] 恒为0（无距离0的负/正矿洞）。

通过上述策略，代码高效覆盖所有可能路径，确保在约束条件下最大化矿洞挖掘数量。