CSES入门题Increasing Array求解求助（C++实现）

核心解题逻辑 #

题目明确只能通过给元素加1的操作将数组转为非递减数组，最小操作次数的计算逻辑如下：

• 遍历数组，维护一个记录「前一个元素调整后最终值」的变量prev
• 对当前元素curr：
  • 若curr < prev：需要把curr提升到prev的数值，操作次数累加prev - curr，同时将curr更新为prev
  • 若curr >= prev：直接更新prev为当前元素的数值
• 最终累加的总次数就是答案

你之前的典型错误点 #

1. 完全误解操作规则：第一次用交换逻辑是彻底偏离题目要求——题目不允许交换元素，只能对元素执行递增操作
2. 数据类型溢出：总操作次数可能极大（比如n=1e5时，单次调整可能需要加1e9），必须用long long存储总次数，用int会直接溢出导致结果错误
3. 未维护调整后的前元素状态：如果遍历过程中只拿原数组的前一个元素比较，而非调整后的最终值，会导致计算偏差

正确的C++代码示例 #

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    long long total_ops = 0;
    long long prev_val = arr[0];
    for (int i = 1; i < n; ++i) {
        if (arr[i] < prev_val) {
            total_ops += prev_val - arr[i];
            arr[i] = prev_val;
        }
        prev_val = arr[i];
    }
    
    cout << total_ops << endl;
    return 0;
}

测试用例验证（输入：6 10 4 10 2 8 9 2 7 7） #

步骤分解：

1. 初始prev_val=6，总操作0
2. 10≥6 → 更新prev_val=10，操作0
3. 4<10 → 加6次，总操作=6，arr[2]变为10，更新prev_val=10
4. 10≥10 → 更新prev_val=10，操作0
5. 2<10 → 加8次，总操作=14，arr[4]变为10，更新prev_val=10
6. 8<10 → 加2次，总操作=16，arr[5]变为10，更新prev_val=10
7. 9<10 → 加1次，总操作=17，arr[6]变为10，更新prev_val=10
8. 2<10 → 加8次，总操作=25，arr[7]变为10，更新prev_val=10
   9.7<10 → 加3次，总操作=28，arr[8]变为10，更新prev_val=10
   10.7<10 → 加3次，总操作=31 → 最终结果与预期一致

内容的提问来源于stack exchange，提问作者NoWar