題目來自DOTCPP：
思路：
①每次找到數列中的最小值下標，然后用狀態數組st標記它，相當與刪除它，之后就不會訪問它。
②對最小值下標左邊和右邊判斷一下，看有沒有數字，如果有就把最小值加到兩邊第一個數字。
暴力代碼如下（會超時）：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+10;int n, k;
int arr[N];
bool st[N];//記錄一個數字有沒有選過signed main(){cin >> n >> k;for(int i = 1; i <= n; i++) cin >> arr[i];for(int i = 1; i <= k ; i++){//找到最小值在數組中的位置int minv = 1e18;int ssmin = -1;for(int j = 1; j <= n; j++){if(minv > arr[j] && !st[j]){//更新最小值的坐標ssmin = j;minv = arr[j];}}//將最小值標記st[ssmin] = true;//將最小值加到右邊第一個數字if(ssmin > 1 ){for(int m = ssmin; m >= 1; m--){if(!st[m]){arr[m] += minv;break;}}}//將最小值加到左邊第一個數字if(ssmin < n){for(int k = ssmin; k<= n; k++){if(!st[k]){arr[k] += minv;break;}}}}for(int i =1; i <= n; i++){if(st[i]) continue;cout << arr[i] << " ";}return 0;
}
代碼優化：
上面代碼K次排序，在N個數中找到最小值。時間復雜度爆炸，我們需要對它優化。需要用到小根堆來記錄最小值的下標，同時對于最小值的下標兩邊，我們用鏈表記錄，會減少很多時間。
小根堆+鏈表：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+20;#define x first
#define y second
typedef pair<int, int> PII;int n, k;
int arr[N];//數據
//優先隊列-小根堆
//q第一個參數為值，第二個參數為這個值的下標
priority_queue<PII, vector<PII>, greater<PII>> q;
//鏈表
int l[N], r[N];signed main(){cin >> n >> k;for(int i = 1; i <= n; i++){cin >> arr[i];//存入優先隊列q.push({arr[i],i});//記錄左右兩邊坐標 最左邊和最右邊都記為-1l[i] = i-1;r[i] = i+1;//最右邊記為-1if(r[i] == n+1){r[i] = -1;}}//開始K次操作while(k--){//取出最小值auto t = q.top();//刪除最小值q.pop();//最小值的 值、坐標int num = t.x, pos = t.y;//后面pos兩邊第一個數加上num后，q中的值發生改變//我們沒有記錄 因此我們要判斷一下if(num != arr[pos]){//我們之前刪除了這個數，然后在更新一下//因為我們取得值不是更新過的值（這個值是原來的，沒有加上最小值）q.push({arr[pos], pos});k++;//**同時這次操作要重新來過 k++continue;}//對刪除的數標記一下，方便輸出arr[pos] = -1;//對左右兩邊第一個數加上最小值//對刪除最小值下標的鏈表更新,即pos左邊和右邊鏈接在一起if(l[pos] >= 1){//左邊數加上最小值arr[l[pos]] += num;//pos左邊鏈接到pos右邊r[l[pos]] = r[pos];}if(r[pos] >= 1){//右邊數加上最小值arr[r[pos]] += num;//pos右邊鏈接到pos右邊l[r[pos]] = l[pos];}} for(int i = 1; i <= n; i++){if(arr[i] != -1){cout << arr[i] << " ";}}return 0;
}注意：代碼中pos左右兩邊的數的下標，在arr數組中加上最小值之后，在q中是沒有更新的，因此我們要判斷一下，q中取出最小值的下標和我們在arr數組中相同下標的元素的值是否相等，不相等的話，就要更新一下。同時，這次操作沒有對pos兩邊的元素進行操作，則k++。
)
)
