题目传送门
题目思路
简单来说就是两个数的差。b[1]一定是等于a[1]的，因为b[1]=a[1]-a[0]，而
a[0]=0,所以b[1]=a[1]。
了解了概念，我们看一下差分和原序列之间有什么关系
把序列a的区间[l,r]+d（或者说a[l]+d,a[l+1]+d,a[l+2]+d+....+a[r]+d的
话，那么这个序列a的差分序列b的变化就为b[l]+d,b[r+1]-d。为什么呢？举个例子
原序列a：1 3 4 2 1，其差分序列b:1 2 1 -2 -1
把区间[2,4]+2，得到的序列a应该是1 5 6 4 1
再看差分序列b，根据我们上面说的公式，a[2,4]+2应该等于b[2]+2,b[5]-2;
差分序列b变为：1 4 1 -2 -3
到底是不是这样呢？我们根据差分的概念倒推回去看看
由于b[1]=a[1]，且b[1]=1，所以a[1]=1;
b[2]=4，则a[2]-a[1]=b[2]=4;由于a[1]=1，得出a[2]=5;
b[3]=1，则a[3]-a[2]=1，由于a[2]=5，得出a[3]=6;
b[4]=-2,则a[4]-a[3]=-2，由于a[3]=6，得出a[4]=4;
b[5]=-3,则a[5]-a[4]=-3，由于a[4]=4，得出a[5]=1;
由差分序列倒推回来得到的原序列是1 5 6 4 1，完全符合我们之前得到的，说明这
个公式是正确的。
直观点说，原序列1 3 4 2 1，把区间[2,4]+2，得到的序列a是1 5 6 4 1
可以发现，a[2,4]中的差是不变的，因为他们同时加了一个数，变化的是a[l-1]和
a[l]之间的差以及a[r]和a[r+1]之间的差，这样一来，就很好推出这个差分序列公式
下面是这个公式的延伸
如果a[l,r]+1，则b[l]+1，b[r+1]-1;
如果a[l,r]-1，则b[l]-1，b[r+1]+1;
如果a[l,n]+1(l <= n - 1)，则b[l]+1，其余不变，因为b[n+1]已越界无意义
如果a[l,n]-1(l <= n - 1),则b[l]-1，其余不变，因为b[n+1]已越界无意义
下面看一下这个题该怎么做
要使得序列的数全部相等，其实就是让他们之间的差全为0，也就是差分序列的除了第
一项每一项都是0，为什么除了第一项呢，因为b[1]=a[1]-a[0]，而a[1]是开头的数
我们把问题转化成了让差分序列除第一项全等于0之后，继续思考
由于题目要求最少的步骤，我们可以考虑，如果差分序列里有一个正数和一个负数
（出现的顺序无所谓），那么我们优先对这个正数和负数进行操作，为什么呢？因为
我们有以下两个公式
如果a[l,r]+1，则b[l]+1，b[r+1]-1
如果a[l,r]-1，则b[l]-1，b[r+1]+1
正数-1，负数+1，这样相当于一步里作用了两步，比让正数一个个-1和让负数一个个
+1快多了
那么我们可以进行多少种这样的操作呢？
我们可以令差分序列里正数绝对值的总和为p，负数绝对值总和为q
可以进行这样一步顶两步的操作就是min（p，q），因为这种操作正数负数是一一配
对的，当少的那个先用完了，剩下的没有可以配对的了，只能一步步减或一步步加。
所以我们总共要进行的操作就为min（p，q）+abs（p-q），也就是max（p，q）
第一问完成，看第二问
保证最少次数的前提下，最终得到的数列有多少种？
得到的数列有多少种，其实就是问的b[1]可以有多少种
我们上述所有操作是与b[1]无关的，因为我们的目标是让除了b[1]以外的项变0，所
以我们上述的操作没有考虑到b[1]，b[1]怎么变，与我们求出的最小步骤无关
那么，我们怎么知道b[1]有几种呢？很简单，其实就是看看有几种一步步减或一步步
加的操作数，因为我们一步步加的时候（假设我们现在的操作对象下标为i），
可以这样操作，b[1]-1,b[i]+1
一步步减的时候可以这样操作，b[1]+1,b[i]-1
（注意，一个差分序列里一步步操作的时候只可能一步步加或一步步减，不可能一步
步加和一步步减同时存在）
所以说，有几步一步步的操作就有几种情况+1，为什么+1呢，因为这个b[1]本身就有
一个值啊！就算你不对他进行任何操作，它自己也有一种情况。
一加一减（也就是我们所说的一步顶两步的操作）操作数为min（p，q）
那么一步步的操作数就为max（p，q）-min（p，q）=abs（p，q）
AC代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n + 2);
vector<int> dp(n + 2);
a[0] = 0;
dp[0] = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
dp[i] = a[i] - a[i - 1];
}
dp[n + 1] = 0;
long long zs = 0, fs = 0;
for (int i = 2; i <= n + 1; i++)
{
if (dp[i] > 0)
zs += dp[i];
else
fs -= dp[i];
}
cout << max(zs, fs) << endl;
cout << abs(zs - fs) + 1 << endl;
return 0;
}