题目描述

本题求改变连续的区间，最少经过多少次操作，可以使所有数字一样大

样例

输入样例：
4
1
1
2
2

输出样例：
1
2

可以选用差分的方法来写，b[i] = a[i] - a[i - 1];
本题使区间差分数组b[2]~b[n]一样大即可，怎么实现呢？
定义p和q，统计差分数组的正数负数有多大（从b[2]开始），通过改变它们来达到差分数组b[2]~b[n]一样大，需要多少操作次数，例如正数之和大，我们可以使（负数）那一部分顺应正数，使用负数加上一些数，最后将那些正数中“佼佼者”在减去一些数来顺应“大部队”。

操作次数为min(p, q) + abs(p - q)

方案数有多少呢，方案数为abs(p - q) + 1，为什么呢？
正如输入样例，我们可以改变它们都为1，也可以都为2，如果样例改为1，1，2，3，2，1 则b[2] = 0, b[3] = 1, b[4] = 1, b[5] = -1, b[6] = -1,我们为了只用两次操作，只能将它们都更改为1

代码演示

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

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

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        scanf("%lld", &a[i]), b[i] = (LL)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];
    }

    cout << max(p, q) << endl;
    cout << abs(p - q) + 1 << endl;
}