P10904[蓝桥杯2024省C]挖矿

P10904 [蓝桥杯 2024 省 C] 挖矿 题目描述

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

输入格式

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

第二行包含 n n n 个整数 a 1 , a 2 , ⋯   , a n a_1, a_2,\cdots, a_n a1​,a2​,⋯,an​，相邻整数之间使用一个空格分隔。

输出格式

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

输入输出样例 #1 输入 #1 5 4 0 -3 -1 1 2 输出 #1 4 说明/提示

【样例说明】

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

【评测用例规模与约定】

对于 20 % 20\% 20% 的评测用例， 1 ≤ n ≤ 1 0 3 1 \le n \le 10^3 1≤n≤103； 对于所有评测用例， 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105， − 1 0 6 ≤ a i ≤ 1 0 6 -10^6 \le a_i \le 10^6 −106≤ai​≤106， 1 ≤ m ≤ 2 × 1 0 6 1 \le m \le 2 \times 10^6 1≤m≤2×106。

#include <bits/stdc++.h> using namespace std; const int N = 2e6 + 10; int n, m; vector<int> l(N), r(N); int ans = 0, cnt = 0; int main() { cin >> n >> m; for (int i = 1, x; i <= n; i++) { cin >> x; if (x < 0) { l[-x]++;//不管怎样，应统计成正数，同时也方便计算 } else if (x > 0) { r[x]++; } else { cnt++;//x=0的情况下加一就行，勿遗漏 } } for (int i = 1; i <= m; i++) {//前缀和 l[i] += l[i - 1]; r[i] += r[i - 1]; } for (int i = 1; i <= m; i++) { int 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); } cout << ans + cnt << endl; return 0; }