自动搬运

查看原文

来自洛谷，原作者为

	Castorice 「如果枯萎不可避免，至少让我们的告别…更美一些。」

搬运于2025-08-24 23:02:22，当前版本为作者最后更新于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;
}