C. Helping the nature (CF) difference

  Original link ：Problem - C - Codeforces

The main idea of the topic ： Give you an array a, The range of each number is −1e9≤ai≤1e9, Each operation can be selected from the following operations ：

1） hold a1 ... ai Subtract one from all the numbers

2) hold ai ... an Subtract one from all the numbers

3） hold a1...an Add one to all the numbers in the whole array

Ask you the minimum number of operations so that each element in the entire array is 0？

Ideas ：

One segment is subtracted / Add operation ----> Difference

So by the a[i] have to b[i] Array ( The difference between every two adjacent elements ）, Because all numbers will eventually become 0, therefore b[] The array should also be all 0, So it can be used 1 or 2 operation , From back to front b[] All become 0, After each change ,b[i] After that b[j] All for 0 了 , That's the array a[] It will all be the same ; Note that if b[i] here >=0, So it is to subtract the following part 1, So don't worry about ; But if b[i]<0, Is to start from a[1] To a[i] All minus 1, therefore a[1] Will change , Here we need to change a[1]. Finally, put b[n] To b[2] It's over , Look again a[1] And 0 The difference between , It can be used separately 2 and 3 The operation adds or subtracts the entire array to 0！

AC Code ：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define PII pair<int,int>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for(int i = n; i >= 1; ++i)

using namespace std;

const double pi = acos(-1.0);

const int N = 2e5 + 10;
ll a[N], b[N];

int main()
{
    int t, n;
    cin >> t;
    while(t--)
    {
        cin >> n;
        ll res = 0;
        rep(i, n) cin >> a[i], b[i] = a[i] - a[i - 1];
        for(int i = n; i > 1; i--)
        {
            if(b[i] >= 0) res += b[i];
            else res -= b[i], b[1] += b[i];
        }
        res += abs(b[1]);
        cout << res << endl;
    }
    return 0;
}