Acwing 100.增减序列

题目

https://www.acwing.com/problem/content/102/

由于题意为每次加一或减一，所以不需要用高级的数据结构。

首先是思考怎么能实现最小次数。

题意描述的是差分的过程，因此这一题肯定和差分有关系，首先根据已知数组构造差分数组，
可以发现差分数组中有正有负，根据差分的性质可以肯定分别选择正负作为差分加减的左右
极可以在最少的次数内将差分数组全部转化为只有正数或负数的数组。此时所需步数为min(
sum(正数)，abs(sum(负数)))

第二步容易发现，剩下的正数或负数可以通过a[1]或a[n+1]来转化为0，因为a[1]/a[n+1]不会
改变差分数组的结果。此时需要的步数是多少呢？由于通过第一步我们已经将部分正负数抵消，
因此现在将所有置为0所需要的步数只有(sum(正数)-abs(sum(负数))了。

同时由于第二步可以在不同的位置停下，因此最多情况也是这些。

代码如下

#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
const int N = 1e5+10;
int f[N];
int main()
{
    int n;
    std::cin>>n;
    for(int i=1;i<=n;i++) std::cin>>f[i];
    
    ll y=0,t=0;
    for(int i=2;i<=n;i++) {
        int c = f[i]-f[i-1];
        if(c>0) y+=c;
        else t-=c;
    }
    
    std::cout<<std::max(y,t)<<std::endl<<std::abs(y-t)+1;
    
    return 0;
}