给定一个长度为 n的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
tips：
1.进行问题求解的等价转换---对a数组区间的操作等价转换为对b数组其中两个元素（端点）的操作
2.数据范围求和后可能爆，用 long long
3.变成一样的，只考虑2...n---由b数组的定义可知，b[1]=a[1]；其他b[i]=a[i]-a[i-1];
代码中直接用a的空间来存b了，b[i]存储记录的是a[i]比a[i-1]大的相关信息，对a[i]和a[i-1]的相对大小关系进行了建模。
4.差分+贪心；差分：前缀和的逆运算
5.对每次操作的区间进行了范围讨论[i,j]是否在[2,n];
6.求最小次数下的方案数最后成为一个排列组合问题
7.疑问：为什么不考虑最后m对应的b数组的几个位置？？
其他好的题解：
ref1
ref2
#include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010; int a[N]; int main(){ int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i]; for(int i = n; i > 1; i --) a[i] = a[i] - a[i-1];//倒着处理--mark LL pos = 0, neg = 0; for (int i = 2; i <= n; i++ ) if (a[i] > 0 ) pos += a[i]; else neg-=a[i]; //求负数的绝对值之和 cout << min(pos, neg) + abs(pos - neg) << endl; cout << abs(pos - neg) + 1 << endl; return 0; }