C. Helping the Nature（cf）差分

 原题链接：Problem - C - Codeforces

题目大意：给你一个数组a，其中每个数的范围是−1e9≤ai≤1e9,每一次操作可以在以下操作中选择：

1）把a1 ... ai所有数减一

2) 把ai ... an所有数减一

3）把a1...an整个数组中所有数加一

问你最少操作次数使得整个数组中每个元素都为0？

思路：

一段进行减操作/加操作 ----> 差分

所以由a[i]得b[i]数组(每两个相邻的元素之间的差值），因为所有数最后都要变成0，所以b[]数组也应该全为0，所以可以用1或2操作，从后往前把b[]全变为0，每次变完，b[i]之后的b[j]都为0了，也就是数组a[]后面都会变成一样的了；注意如果b[i]此时>=0,那么就是将后面部分减1，所以不用管；但是如果b[i]<0，就是把从a[1]到a[i]全部减1，所以a[1]会变,这里要改变a[1]。最后把b[n]到b[2]变完了，再看a[1]与0的差别，可以分别用2和3操作把整个数组全加或全减变为0！

AC代码：

#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;
}