0挖矿 - 蓝桥云课
问题描述
小蓝正在数轴上挖矿,数轴上一共有 n 个矿洞,第 i 个矿洞的坐标为 ai。小蓝从 0 出发,每次可以向左或向右移动 1 的距离,当路过一个矿洞时,就会进行挖矿作业,获得 1 单位矿石,但一个矿洞不能被多次挖掘。小蓝想知道在移动距离不超过 m 的前提下,最多能获得多少单位矿石?
输入格式
输入的第一行包含两个正整数 n,m,用一个空格分隔。
第二行包含 n 个整数 a1,a2,…,an,相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入
5 4
0 -3 -1 1 2
样例输出
4
样例说明
路径:0 → -1 → 0 → 1 → 2,可以对 0,-1,1,2 四个矿洞挖掘并获得最多 4 块矿石。
评测用例规模与约定
- 对于 20% 的评测用例,1 ≤ n ≤ 10³;
- 对于所有评测用例,1 ≤ n ≤ 10⁵,-10⁶ ≤ ai ≤ 10⁶,1 ≤ m ≤ 2 × 10⁶。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 3s | 512M |
Python3 | 10s | 512M |
PyPy3 | 3s | 512M |
Go | 5s | 512M |
JavaScript | 5s | 512M |
思路:
代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MAX_M = 2e6 + 10;
ll a[MAX_M],b[MAX_M];//a为右,b为左
ll pre_a[MAX_M],pre_b[MAX_M];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll n, m,cnt =0;cin >> n >> m;for (ll i = 0; i < n; ++i) {ll x;cin >> x;if (x > 0 && x <= m) {a[x]++;} else if(x < 0 && -x <= m) {b[-x]++;}else if(x == 0)cnt ++;}pre_a[0] = a[0];pre_b[0] = b[0];for (ll i = 1; i < MAX_M; ++i) {pre_a[i] = pre_a[i - 1] + a[i];pre_b[i] = pre_b[i - 1] + b[i];}ll ans = 0;// 处理先向左走i步,再向右走剩余步数的情况for (ll i = 0; i <= m; ++i) {if (m - 2 * i < 0) continue;ans = max(ans, pre_b[i] + pre_a[m - 2 * i]);}// 处理先向右走i步,再向左走剩余步数的情况for (ll i = 0; i <= m; ++i) {if (m - 2 * i < 0) continue;ans = max(ans, pre_a[i] + pre_b[m - 2 * i]);}cout << ans + cnt << endl;return 0;
}