[藍橋杯] 挖礦（CC++雙語版）

題目鏈接

? ? ? ? ? P10904 [藍橋杯 2024 省 C] 挖礦 - 洛谷

題目理解

? ? ? ? 我們可以將這道題中礦洞的位置理解成為一個坐標軸，以題目樣例繪出坐標軸：

樣例：

? ? ? ? 輸入的5為礦洞數量，4為可走的步數。第二行輸入是5個礦洞的坐標。輸出結果為在要求步數內最多可采集到的單位數量的礦石。

?????????我們下面來對樣例進行分析：

? ? ? ? 初始狀態如下：

? ? ? ? 初始位置為0，剩余步數為4。當坐標0有礦石時，不需要消耗步數，可直接獲取礦石：

? ? ? ? 我們向-1移動：

????????此時若是向負軸移動，我們只能采到1個單位的礦石，正軸方向可以采到2個單位。于是我們向正軸方向進發：

? ? ? ? 繼續進發：

????????繼續：

?

解題思路

? ? ??——(篇幅較長，大家也可以先看詳細注釋后的代碼，遇到不懂的地方再看解題思路)——

? ?一、核心思路概述

????????解決該挖礦問題的核心在于合理利用數軸上礦洞的分布信息以及移動距離限制，通過巧妙的統計和計算，找出在給定移動距離內能夠挖掘到最多礦石的方法。主要步驟包括對礦洞坐標的分類統計、構建前綴和數組以快速計算區間礦洞數量，以及全面考慮不同移動策略下的礦石獲取情況。

? ?二、具體步驟解析

? ? （一）輸入數據處理

1. 讀取礦洞數量 n 和最大移動距離 m，這兩個參數將決定后續計算的范圍和約束條件。

2. 依次讀取 n 個礦洞在數軸上的坐標值，對于每個坐標值進行如下分類處理：

????????如果坐標值為 0，說明該礦洞位于小藍的起始位置，直接將此類礦洞的計數變量 s 加 1。這些礦洞無需移動即可挖掘，對最終結果有直接貢獻。
????????如果坐標值不為 0，且其絕對值小于等于 m，則根據坐標值的正負性分別處理。
????????若坐標值為負數，將其對應在負半軸的位置索引處的計數器（例如數組 l）加 1，用于統計負半軸上在移動距離范圍內的礦洞數量。
????????若坐標值為正數，將其對應在正半軸的位置索引處的計數器（例如數組 r）加 1，用于統計正半軸上在移動距離范圍內的礦洞數量。

? （二）構建前綴和數組

????????1. 對于記錄負半軸礦洞數量的數組 l，從索引 1 開始到 m，依次計算前綴和。即 l[i] = l[i - 1] + l[i]，這樣 l[i] 就表示數軸負半軸上從 -1 到 -i 位置的礦洞總數。通過前綴和，我們可以在后續計算中快速得到負半軸某一區間內的礦洞數量。

????????2. 同理，對于記錄正半軸礦洞數量的數組 r，也從索引 1 開始到 m，計算前綴和 r[i] = r[i - 1] + r[i]，使得 r[i] 表示數軸正半軸上從 1 到 i 位置的礦洞總數。

? （三）計算最大礦石獲取量

1. 初始假設：

????????首先假設最大礦石獲取量 ans 為只在正半軸或只在負半軸移動時能夠挖掘到的最大礦石數。即 ans = max(r[m], l[m])，這是一種簡單的初步情況考慮，因為在某些情況下，僅在一個方向移動可能就能夠獲取最多的礦石。

2. 考慮混合移動策略：

????????通過循環遍歷 i 從 1 到 m / 2（因為左右移動距離之和不能超過 m，所以 i 最大取到 m / 2），嘗試不同的左右移動組合。 - 對于每一個 i 值，計算兩種混合移動策略下能夠挖掘到的礦石數：
????????先向右移動 i 單位距離，再向左移動 m - 2 * i 單位距離時，能夠挖掘到的礦石數為 sr = r[i] + l[m - 2 * i]。這里 r[i] 表示向右移動 i 單位距離過程中挖掘到的正半軸礦洞數，l[m - 2 * i] 表示向左移動 m - 2 * i 單位距離過程中挖掘到的負半軸礦洞數。 - 先向左移動 i 單位距離，再向右移動 m - 2 * i 單位距離時，能夠挖掘到的礦石數為 sl = l[i] + r[m - 2 * i]。這里 l[i] 表示向左移動 i 單位距離過程中挖掘到的負半軸礦洞數，r[m - 2 * i] 表示向右移動 m - 2 * i 單位距離過程中挖掘到的正半軸礦洞數。
????????每次計算出 sr 和 sl 后，更新最大礦石獲取量 ans，即 ans = max(ans, sr, sl)，取當前的 ans、sr 和 sl 中的最大值作為新的 ans。

3. 加上起始點礦洞數量：

????????最后，將起始點（坐標為 0）的礦洞數量 s 加到 ans 中，因為這些礦洞在初始位置就可獲取，無需移動。此時得到的 ans 即為在移動距離不超過 m 的前提下，小藍最多能獲得的礦石單位數量。通過以上步驟，我們可以全面且高效地解決在給定條件下的挖礦問題，找到獲取最多礦石的方案。

完整代碼（詳細注釋）

? ? ? ? 本文由于用到了std庫中的一些函數，所以作者最開始采用了C++，C語言代碼作者用ai轉化并確保代碼無誤后給大家放在了下面。

????1.C++代碼

#include <bits/stdc++.h>// 定義 solve 函數來解決挖礦問題
void solve() 
{int n, m;// 從標準輸入讀取礦洞數量 n 和最大移動距離 mstd::cin >> n >> m;// s 用于記錄坐標為 0 的礦洞數量int s = 0;// 定義兩個靜態數組 l 和 r 來分別記錄負半軸和正半軸礦洞的前綴和// 數組大小為 m + 1，初始化為 0int l[10000001] = {0};int r[10000001] = {0};// 遍歷每個礦洞for (int i = 0; i < n; ++i) {int x;// 讀取當前礦洞的坐標std::cin >> x;// 如果礦洞坐標的絕對值小于等于最大移動距離 m 且為負數//abs為絕對值函數if (std::abs(x) <= m && x < 0){// 對應負半軸的位置計數加 1l[-x]++;}// 如果礦洞坐標的絕對值小于等于最大移動距離 m 且為正數else if (std::abs(x) <= m && x > 0) {// 對應正半軸的位置計數加 1r[x]++;}// 如果礦洞坐標為 0else if (x == 0) {// 坐標為 0 的礦洞數量加 1s++;}}// 計算負半軸礦洞的前綴和for (int i = 1; i <= m; ++i){l[i] += l[i - 1];}// 計算正半軸礦洞的前綴和for (int i = 1; i <= m; ++i) {r[i] += r[i - 1];}// 先假設最大礦石數為只走正半軸或只走負半軸能挖到的最大礦石數int ans = std::max(r[m], l[m]);// 嘗試不同的左右移動組合，i 表示先向一個方向移動的距離for (int i = 1; i <= m / 2; ++i) {// 先向右移動 i 的距離，再向左移動 m - i * 2 的距離能挖到的礦石數int sr = r[i] + l[m - i * 2];// 先向左移動 i 的距離，再向右移動 m - i * 2 的距離能挖到的礦石數int sl = l[i] + r[m - i * 2];// 更新最大礦石數ans = std::max({ans, sr, sl});}// 加上坐標為 0 的礦洞數量ans += s;// 輸出最大能獲得的礦石數std::cout << ans << '\n';
}int main() 
{solve();return 0;
}

?????2.C語言代碼?

#include <stdio.h>
#include <math.h>#define MAX_M 10000001// 定義 solve 函數來解決挖礦問題
void solve() {int n, m;// 從標準輸入讀取礦洞數量 n 和最大移動距離 mscanf("%d %d", &n, &m);// s 用于記錄坐標為 0 的礦洞數量int s = 0;// 定義兩個靜態數組 l 和 r 來分別記錄負半軸和正半軸礦洞的前綴和// 數組大小為 MAX_M，初始化為 0int l[MAX_M] = {0};int r[MAX_M] = {0};// 遍歷每個礦洞for (int i = 0; i < n; ++i) {int x;// 讀取當前礦洞的坐標scanf("%d", &x);// 如果礦洞坐標的絕對值小于等于最大移動距離 m 且為負數if (abs(x) <= m && x < 0) {// 對應負半軸的位置計數加 1l[-x]++;}// 如果礦洞坐標的絕對值小于等于最大移動距離 m 且為正數else if (abs(x) <= m && x > 0) {// 對應正半軸的位置計數加 1r[x]++;}// 如果礦洞坐標為 0else if (x == 0) {// 坐標為 0 的礦洞數量加 1s++;}}// 計算負半軸礦洞的前綴和for (int i = 1; i <= m; ++i) {l[i] += l[i - 1];}// 計算正半軸礦洞的前綴和for (int i = 1; i <= m; ++i) {r[i] += r[i - 1];}// 先假設最大礦石數為只走正半軸或只走負半軸能挖到的最大礦石數int ans = (r[m] > l[m]) ? r[m] : l[m];// 嘗試不同的左右移動組合，i 表示先向一個方向移動的距離for (int i = 1; i <= m / 2; ++i) {// 先向右移動 i 的距離，再向左移動 m - i * 2 的距離能挖到的礦石數int sr = r[i] + l[m - i * 2];// 先向左移動 i 的距離，再向右移動 m - i * 2 的距離能挖到的礦石數int sl = l[i] + r[m - i * 2];// 更新最大礦石數if (sr > ans) ans = sr;if (sl > ans) ans = sl;}// 加上坐標為 0 的礦洞數量ans += s;// 輸出最大能獲得的礦石數printf("%d\n", ans);
}int main() {solve();return 0;
}

???????AC拿下！

疑難解答?

? ? 1.max函數的運用

? ? ? ? 用于比較出幾個數中最大的數字，大家可以簡單理解為兩個數比較就不需要大括號，如果三個及以上的話需要大括號。

兩個參數比較：當比較兩個值時，使用?std::max(a, b)?形式，這里?a?和?b?是要比較的對象，不需要大括號。比如?int num1 = 5, num2 = 3; int maxNum = std::max(num1, num2);?。
三個及以上參數比較：對于三個或更多值，常使用接收初始化列表形式的重載，即?std::max({val1, val2, val3,...})?，需要用大括號把這些值組成初始化列表傳遞給函數。像?int num1 = 1, num2 = 2, num3 = 3; int maxNum = std::max({num1, num2, num3});?。

———（如有問題，歡迎評論區提問）———