【差分】Acwing100增减序列

【差分】Acwing100增减序列

原题链接

思路：
假设差分数组为b
要使最后的数都一样，那么b数组中的b2到bn 一定全为0最后
因为

b2 = a2-a1;
b3 = a3-a2;
......
bn = an-an-1;

如果全0 的话， a1=a2=a3=…=ana1=a2=a3=…=an
所以我们可以用贪心的思想，来使得b中所有数变成零。 因为
每次我们在原数组中的一个区间内，同时加一或者同时减1，相当于做b[L]++,b[R+1]–;
也就是我们在b数组中，每次都要找到一个数+1，一个数-1，最后的目标是b数组全部等于0。
那么，贪心,每次 *** 作的时候，让b数组中的负数++，正数–，
但是最终结果可能依然不是全 0 的
还剩下abs(pos-neg)次 *** 作，每个 *** 作就是在b中找到一个数+1，再找一个数-1
我们知道，最后整个原序列等于多少，取决与第一个数的值，所以我们剩下的abs(pos-neg)次 *** 作，我们每一次找b[1]或者b[n+1]与之配对，这样不会对b数组产生影响。
所以最后对应的原数组a[1]的值，有abs(pos-neg)+1次可能，因为有可能对b[1] *** 作0次。

ans1=min(pos,neg)+abs(pos−neg)
ans2=abs(pos−neg)+1

代码

#include
#include
#include

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=n; i>=1; i--) a[i]-=a[i-1]; //求差分数组
    
    LL pos=0, neg=0; //分别求整数和负数
    for(int i=2; i<=n; i++)
        if(a[i] > 0) pos+=a[i];
        else neg -= a[i];

    cout << min(pos, neg) + abs(pos - neg) << endl;
    cout << abs(pos - neg) + 1 << endl;

    return 0;
}