OD Machine Test2

// 一组非负整数的数据，0元素会把数据分段，然后最多有k次机会，
// 每次可以把一段的数据每一个值都减一。 
// 问，这k次机会使用完之后，这组数据的最小和
struct Solution41 {
    vector<vector<int>> res;
    void fenduan(vector<int>& arr, int s, int e) {
        for(int i = s; i <= e; ++i) {
            vector<int> seg(2, 0);
            if(arr[i] == 0) continue;           // 遇到0跳过
            seg[0] = i;                         // 连续非0段的第一个下标
            int j = i;
            while(j <= e && arr[j] != 0) j++;   // 寻找连续非0段的最后一个下标
            if(j == e) {                        // 直到最后一个也不为0
                seg[1] = j;
            } 
            else {
                seg[1] = j - 1;
            }
            res.push_back(seg);
            i = j;
        }
    }
    int arrSum(vector<int>& arr) {
        int sum = 0;
        for(auto it : arr) sum+=it;
        return sum;
    }
    int fun(vector<int>& arr, int k) {
        int sum  = arrSum(arr);
        int n = arr.size();
        fenduan(arr, 0, n-1);

        int cnt = 1;
        while(cnt <= k) {
            int n = res.size();
            int maxlen = 0, idx = 0;
            for(int i = 0; i < n; ++i) {
                if(maxlen <= res[i][1] - res[i][0] + 1) {
                    maxlen  = res[i][1] - res[i][0] + 1;
                    idx = i;
                }
            }
            
            int minv = INT_MAX;
            int l = res[idx][0], r = res[idx][1];
            for(int i = l; i <= r; ++i) {
                minv = min(minv, arr[i]);
            }
            for(int i = l; i <= r; ++i) {
                arr[i] -= minv;
            }
            res.erase(idx);
            fenduan(arr, l, r);

            if(cnt + minv <= k){
                sum -= maxlen*minv;
                cnt = cnt + minv + 1;
            }
            else {
                minv = k - cnt;
                sum -= maxlen*minv;
                break;
            }
        }

    }
};