减成一

题目：减成一
来源：“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛)

解题思路

题目：存在 n 个数，每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作，可以让所有数都变成 1。

① 以 1 所在的位置作为区间的边界，但不包括该位置。
② 遍历区间得到区间的最小值 mini，将区间中的每个数减去 mini - 1，并将该值计入结果 ans。
③ 此时，原来区间最小值所在位置的数字变成 1，继续步骤①，直至所有数都变成 1。

C++代码

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

int ans;

void opCnt(vector<int>& arr, int left, int right){
    if(left > right)
        return;
    if(left == right){
        ans += arr[left] - 1;
        return;
    }
    vector<int> v;
    v.push_back(left);
    int mini = arr[left];
    for(int i=left+1; i<=right; ++i){
        if(arr[i] < mini){
            v.clear();
            v.push_back(i);
            mini = arr[i];
        }
        else if(arr[i] == mini){
            v.push_back(i);
        }
    }

    int minus = mini - 1;
    ans += minus;
    for(int i=left; i<=right; ++i){
        arr[i] -= minus;
    }
    opCnt(arr, left, v[0]-1);
    for(int i=0; i<v.size()-1; ++i){
        opCnt(arr, v[i]+1, v[i+1]-1);
    }
    opCnt(arr, v.back()+1, right);
}

int main(){
    int t;
    cin >> t;
    while(t){
        int n;
        cin >> n;
        vector<int> arr(n);
        for(int i=0; i<n; ++i)
            cin >> arr[i];
        ans = 0;
        opCnt(arr, 0, n-1);
        cout << ans << endl;
        --t;
    }
    return 0;
}