AcWing 100. IncDec序列[差分]

原题传送门：https://www.acwing.com/problem/content/description/102/
【题目大意】
给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
【输入格式】
第一行输入正整数n。
接下来n行，每行输入一个整数，第i+1行的整数代表ai。
【输出格式】
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
【数据范围】
0<n≤105
0≤ai<2147483648

【输入样例】：
4
1
1
2
2
【输出样例】：
1
2

【算法分析】：
　　思路：首先这题一个重点，就是区间[l,r]的修改操作，区间上加减只能只加一或者只减一，因此我们根据差分思想可以考虑在区间[l,r]上l处加一，在r+1处减一，要想所有数变成相同，从差分数组上来看，就是第2~n个位置上的差分数组的数全为0即可。如果不理解看下面这段：
　　差分：对于一个给定的数列A，它的差分数列B定义为, B[1]=A[1],B[i]=Ai−（Ai−1）(2<=i<=n)这里只说性质，也就是把序列A的区间[L,R]加d，也就是把Al,Al+1…Ar都加上d，其实就是它的差分序列B中，Bl+d,Br+1−d，其他的位置统统不改变。因此在这道题目中，我们就可以利用这个非常有用的性质，因为我们只要求A序列中所有的数相同，而不在意这些方案具体是什么，所以说我们就可以转化题目，也就是将对A序列的+1,−1操作，让A序列相同，改成目标把B2,…,Bn变成全0即可，也就是A序列全部相等。而且最后得到的序列，就是这n个B1。
　　按照上面所说的区间修改相当于区间端点的单点修改的性质，那么我们就可以，每一次选取Bi和Bj，2<=i,j<=n,而且这两个数，一个为正数，一个为负数，这样是因为我们要想B数组中这些数变为0，那么正数要减，负数要加，正好成对修改。最后可能会有正数或负数无法找到符号相反的数配对，拿么可以选择B1或者Bn，这两个不影响的数，进行修改。
　　所以分析得到答案就是，设spos为B2~Bn中正数的和，sneg为B2-Bn中负数和的绝对值，中最少操作数min(spos,sneg)+abs(spos−sneg),然后最终序列a可能会有abs(spos−sneg)+1种情况。
　　代码如下：

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n , spos= 0 , sneg = 0,c,a,tmp;
	cin >> n;
	a = 0;
	cin >> a;
	for(int i= 2;i<= n; i++){
		cin >> c;
		tmp = c - a;
		a = c;
		if(tmp > 0) spos += tmp;
		else sneg -= tmp;		
	}
	cout << min(sneg, spos) + abs(spos - sneg) << endl;
	cout << abs(spos - sneg) + 1;
	return 0;
}