題目 3241: 藍橋杯2024年第十五屆省賽真題-挖礦
時間限制: 3s 內存限制: 512MB 提交: 1267 解決: 224
題目描述
小藍正在數軸上挖礦，數軸上一共有 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 ≤ 103 ；

對于所有評測用例，1 ≤ n ≤ 105 ，?106 ≤ ai ≤ 106 ，1 ≤ m ≤ 2 × 106 。

1.分析

? ? ? ? 二分去枚舉范圍的長度即結果。

? ? ? ? 遍歷所有范圍是mid的區間，，如果符合即是合適的。

2.代碼

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 1e5+10;
typedef long long LL;
int a[MAX],n,m;
bool check(int x) {for (int r = x; r < n; r++) { //遍歷所有長度為x的區間LL l = r - x;if (a[r] < 0) {         //在原點左邊情況if (-a[l] <= m) return true;}if (a[l] >= 0) {if (a[r] <= m) return true;}if (a[l] <= 0 && a[r] >= 0) {if (min(a[r],-a[l])+a[r]-a[l] <= m) return true;   }}return false;
}
int main() {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> a[i];}sort(a, a + n);int l = 0, r = n;            //長度最長為nwhile (l < r) {int mid = l + r+1 >> 1;if (check(mid-1)) l = mid;   //因為從0開始下標減一else r = mid - 1;}cout << l << endl;return 0;
}