Submission #72903571

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 加速IO，处理大数据量
void fastIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int main() {
    fastIO();
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<int> R(N);
        for (int i = 0; i < N; ++i) {
            cin >> R[i];
        }

        vector<int> res(N);
        // 第一步：从左到右，确定每列的最大可行值（不超过左列+1，且≤自身R[i]）
        res[0] = R[0];
        for (int i = 1; i < N; ++i) {
            res[i] = min(R[i], res[i-1] + 1);
        }

        // 第二步：从右到左，修正每列的最大可行值（不超过右列+1，且≤自身R[i]）
        for (int i = N-2; i >= 0; --i) {
            res[i] = min(res[i], res[i+1] + 1);
        }

        // 计算总操作次数（原始行号 - 最终行号，累加）
        long long total = 0;
        for (int i = 0; i < N; ++i) {
            total += R[i] - res[i];
        }

        cout << total << '\n';
    }
    return 0;
}

Submission Info

Judge Result