AcWing 100. 增减序列

题目传送门

一、试题分析

因为题意要求，每次都一个区间加上1或者减去1，所以想到了差分。

首先，先对数组/(a/)差分一下，求出差分数组/(b/)，接下来我们的任务就是对/(b[2/sim n]/)全部变成/(0/)（所有的数和/(b[1]=a[1]/)一样)即可。

我们对差分序列/(b/)直接操作，因为一个/(++/)，一个/(–/)，所以我们在/(2 /sim n/)之间要选择一个正数一个负数，一个/(–/)，一个/(++/)，这样就可以尽可能较少操作步骤，剩下的就和/(b[1]/)或者/(b[n+1]/)抵消（不影响整体结果）。

/(p/)为/(b/)当中正数的和。

/(q/)为/(b/)当中负数绝对值的和。

操作步骤/(=min(p,q)+abs(p-q)/)

因为最后可以选择/(b[1]/)或者/(b[n+1]/)抵消，

比如/(b=1 　 0 　 2　 0/)

它可以有
/(3　0　0　0/)（全部和/(b[1]/)消除）
/(2　0　0　0/) (一个/(b[1]/),一个/(b[n+1]/))
/(1　0　0　0/)（全部/(b[n+1]/)）

结果数量=/(abs(p-q)+1/)

二、实现代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;

int n;
int a[N], b[N];

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i] - a[i - 1];
    }

    LL p = 0, q = 0;
    for (int i = 2; i <= n; i++)
        if (b[i] > 0)
            p += b[i];
        else
            q -= b[i];

    printf("%lld/n%lld/n", max(p, q), abs(p - q) + 1);
    return 0;
}