IncDec序列

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

思路：以样例 a[] = (0) 1 1 2 2 为例，显然我们只需要一步操作就可得到1 1 1 1或2 2 2 2

构造出该数组的差分序列：b[] = (0) 1 0 1 0 0，要得到1 1 1 1，则需要的操作是b[3] --, b[5] ++；要得到2 2 2 2，则需要的操作为b[1] ++, b[3] --

可以看到，每次得到一个结果的时候，都有存在一组加减对应关系。如果差分数组中存在正负数，则我们最后要达到的目的是：除了差分数组的第一位b[1]，其之后的都要变为0

设pos(tive)为存第二位开始的正整数之和，neg(ative)为第二位开始的负整数之和：

• 则归零所需的操作次数为：min(pos, neg) + abs(pos - neg)，即先将二者之中较小值归零，将剩下的值单独操作
• 得到的结果可能的种类即为：abs(pos - neg) + 1，即为将剩余的操作归零可以在b[1]或者b[n + 1]两者进行操作

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

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

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    int pos = 0, neg = 0;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }
    for(int i = 2; i <= n; i ++){
        if(b[i] > 0) pos += b[i];
        else neg += -b[i];
    }
    cout << min(pos, neg) + abs(pos - neg) << '\n';
    cout << abs(pos - neg) + 1 << '\n';
    return 0;
}