題意#
給定一個長度為 \( n \) 的陣列。每次操作可將陣列中的某個數字加 1。
求最少操作幾次，才能使陣列變成「非遞減數列」
（即後面的數字大於或等於前面的數字）。
思路#
這題可以使用貪心策略。
因為只能將數字調大，且要求操作次數最少，
所以只有在數字比前一個小的時候，才補足差額。
從左掃描到右，如果當前數字大於或等於前一個數字，就直接略過。
如果當前數字小於前一個數字，為了滿足非遞減條件，
我們須將其擴增至與前一個數字相同。
因此遇到數字比前一個小的情況時，我們將兩者的落差累積至總操作次數中，
並更新當前數字。
陣列長度可達 \( 2 \cdot 10^5 \)，累積的操作次數可能會超過一般 32 位元整數的上限，
因此儲存總和的變數需要宣告為 long long。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, sum = 0; // sum 用來紀錄最少的總操作次數
cin >> n;
vector<int> v(n);
for (auto &i : v) cin >> i; // 讀取初始陣列
// 由左到右掃描整個陣列
for (int i = 1; i < v.size(); i++) {
// 如果這個數字不幸比前一個還要小，代表破壞了非遞減規則
if (v[i-1] > v[i]) {
sum += v[i-1] - v[i]; // 把落差加入總操作次數
v[i] = v[i-1]; // 貪心地把這個數字墊高到跟前一個一模一樣大
}
}
cout << sum; // 輸出累積的總操作次數
}
