题解：P10904 [蓝桥杯 2024 省 C] 挖矿

Castorice · 2024-08-23 19:29:09 · 题解

发现有地方描述不准确，所以重交了一次 QwQ。

考虑记录 l, r 两个前缀和，分别记录负坐标和正坐标，因为 0 坐标矿洞不管怎么走都会挖，所以只需要记录一下 0 坐标的数量，在输出时加上即可。

则可以枚举 i 表示从 0 点出发向左和右走出的距离，并使用前缀和求出能挖多少矿，如果在走一个往返后还有能走的距离（即 m- 2 \times i > 0），就要加上还能走的距离向反方向走能挖到的矿的数量。

时间复杂度：O(m)

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10;
int n, m, l[N], r[N], ans, cnt;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        if (x < 0) {
            l[-x]++;
        } else if (x > 0) {
            r[x]++;
        } else {
            cnt++;
        }
    }
    for (int i = 1; i <= m; i++) {
        l[i] += l[i - 1], r[i] += r[i - 1];
    }
    for (int i = 1, t; i <= m; i++) {
        t = l[i];
        if (m - i * 2 > 0) {
            t += r[m - i * 2];
        }
        ans = max(ans, t);
        t = r[i];
        if (m - i * 2 > 0) {
            t += l[m - i * 2];
        }
        ans = max(ans, t);
    }
    printf("%d\n", ans + cnt);
    return 0;
}