减成一

题意

每次任选一个区间减去一 问最少操作次数使得区间内的值都为一

思路

如果位置i的数 比 i-1更小 那么它对答案没有贡献 因为肯定从i-1开始作为区间的左端点 i这个位置相当于白嫖了减去一 直接跳过
如果位置i的数 比 i-1更大 那肯定还要再选一个区间 i-1这个数变成1了 i这个数不为1 而对答案的贡献就是
两个数之差了

代码

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x, a) memset(x, a, sizeof(x));
#define sca(a) scanf("%d", &a)
#define lowbit(x) x&(-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lson v << 1
#define rson v << 1 | 1
#define pii pair<int, int>

inline void read(int &x)
{
    x=0;
    int flag_read=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag_read=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    x *= flag_read;
}

const int N = 1e6 + 5;

int a[N],sum[N];

int main(){
    ios::sync_with_stdio(0);
    int t;

    cin >> t;

    while(t --){
        int n;

    cin >> n ;

    for(int i = 1;i <= n;i ++){
        cin >> a[i];
    }

    LL res = 0;

    for(int i = 1;i <= n;i ++){
        a[i] --;
        sum[i] = a[i] - a[i - 1];
        res += max(sum[i - 1],0);
    }

    cout << res << '\n';

    }
    return 0;
}