首先来首歌曲来放松一下吧！

题目链接：100. 增减序列

题目背景：

前缀和和差分序列是互逆的！

题目分析处详细解释！

题目描述

给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式

第一行输入正整数n。

接下来n行，每行输入一个整数，第i+1行的整数代表ai。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

0<n≤105
0≤ai<2147483648

输入样例：

1
2
3
4
5
4
1
1
2
2

输出样例：

1
2
1
2

题目分析：

题目要求：

在一个序列内任意选择区间，将区间内的数都进行加一或减一操作，使得最后的序列数字都一样，问对少步数和达到最少步数的方法总数！

解题思路：

先引入差分：

a数组是普通序列，b数组是a数组的差分序列！

差分序列定义：b[i] = a[i] - a[i-1], b[1] = a[1]

然后就是两个定理：

  • b 序列是 a 序列的差分序列（定义就是这样定义的！）
  • a 序列是 b 序列的前缀和序列（开始证明！）

a[i] 可以写为 b[1] + b[i]：如下：

1
2
3
4
5
6
a[1],a[2],.…a[n]
b[i] = a[i] - a[i-1], b[1] = a[1]

a[i] = b[1] + b[2] +.…+ b[i]
     = a[1] + a[2] - a[1] + a[3] - a[2] +.…+ a[i] - a[i-1]
     = a[i]

证明成立！

接下来开始看题！

在一个(L，R)序列上加一个常数 C，相当于：

1
b[L] += C  b[R + 1] -= C;

这个可以稍微想一下：或者那笔画一下！

假设序列从下标为1开始存储！

再想一下：要想全部数变成同样的数，可以让b数组变成什么样？

当然是让 b[1] ~ b[n] 都为0，也就是整个序列此时都是 a[1] ，即 n 个 a[1]！

首先先将差分序列处理出来，我们可以想，既然是区间的端点出进行加一或减一，那么，让一个正数去–，一个负数去++是不是可以更快的达到为0的目的！

所以可以将差分序列的正数和负数都累加一下计算出来！得到两个值！

这样的话：选取一个区间就会使累积的正数（假如是40）和一个负数（假如是34）减一，这样直到其中一方为0，这样正负数匹配就结束了，可能剩下的多出来的一方（不为0的）就需要和b[0]或b[n + 1]来处理。

正负匹配需要最少为 34次，即min(34, 40)

多出来的最少需要 40 - 34 次，即abs(34 - 40)

或者直接这样想，一次就需要正负减1，全部处理完，自然就是最大的数了！就是40次，直接max(34, 40)

所以最少次数为：min(34, 40) + abs(34 - 40) = max(34, 40)

以及最后的方案数：

min(34, 40)是死的，最后不一样的就是多出来的（不为0的）的数的方案，即

abs(40- 34) + 1 ！

yxc大神的视频讲解：点击这里！

题解：

讲解是下标从1开始，我是从0开始，都一样的！

防止溢出，使用 long long！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>

using namespace std;

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

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

int main()
{
    cin >> n; 
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 1; i < n; i++) b[i] = a[i] - a[i - 1];
    
    // positive number, negative number
    LL pos = 0, neg = 0;
    for(int i = 0; i < n; i++)
        if(b[i] > 0) pos += b[i];
        else neg -= b[i];
        
    cout << max(pos, neg) << endl << abs(pos - neg) + 1 << endl;
    return 0;
}