给定一个长度为n的数列a1, a2, ... , an, 每次可以选择一个区间[l,r]，使这个区间内的数都加1或者都减1。
请问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。
第一行一个正整数n 接下来n行,每行一个整数,第i+1行的整数表示ai 。
第一行输出最少操作次数 第二行输出最终能得到多少种结果
4
1
1
2
2
1
2
对于100%的数据，n <= 100000，0 <= ai <= 2147483648。
考虑原数组a(长度为n，下标0到n - 1)的差分数组d:
- d[0] = a[0]
- d[i] = a[i] - a[i - 1]，i属于[1, n - 1]
那么:
- 若数组a的所有元素相同，那么数组d除d[0]外所有元素为0，而d[0]的值就是a的每个元素的值。
- 若数组a在[l, r]区间(l <= r < n - 1)内每个数增加1，则d[l]增加1，而d[r + 1]减少1
- 若数组a在[l, n - 1]区间(l <= n - 1)内每个数增加1，则d[l]增加1，其余不变(n - 1 + 1 = n，d[n]已越界)
- 若数组a在[l, r]区间(l <= r < n - 1)内每个数减少1，则d[l]减少1，而d[r + 1]增加1
- 若数组a在[l, n - 1]区间(l <= n - 1)内每个数减少1，则d[l]减少1，其余不变
对原数组a的差分数组d进行以下3种操作
- d[i]增加1且d[j]减少1，i <= n - 1 && j <= n - 1 && i != j
(一增一减) - d[i]增加1，i <= n - 1
(单独增加) - d[i]减少1，i <= n - 1
(单独减少)
使得数组d除d[0]外所有元素为0。求最少的操作次数，以及在保证最少次数的前提下，最终得到的数组d中，d[0]有多少种不同的值~
那么如何操作呢
由于d[0]不用转换为0，所以对于i属于[1, n - 1]:
若d[i] > 0，则要将其减少为0，可以使用多次d[i]减少1的操作，但是题目要求操作次数最少，所以若存在j != 0使得d[j] < 0，就可以使用d[i]减少1而d[j]增加1的操作，这样比单独让d[i]减少效率更高。
d[i] < 0时同理。
也就是对于每个d[i]，只要它不等于0，就要找d中除d[0]外与d[i]符号相反的数，这样一次操作可以使两个数更接近0；只有在不存在符号相反的数时，才使用单独一个数增加/减少的操作。
那么编程的时候，需要对每个d[i]去找符号相反的数吗，如果这样写，就会开心的TLE了。实际上，我只需要计算出数组d除d[0]外所有元素中，正数之和与负数的绝对值之和，正数之和设为positive，负数绝对值之和设为negative，由于所有正数都需要找负数，而所有负数都要找正数，设positive和negative中大的为max，小的为min，那么max就是所求最少操作次数，其中min次操作为一增一减，max - min次操作为单独增加/减少。
还有一个问题就是d[0]可以有多少种不同的值。我们上面的操作都是不针对d[0]的，因为它不用变为0嘛，但是对于所有的单独一个数增加/减少的操作，可以有一种代替的操作，即:
d[i]增加1，可以通过d[0]减少1且d[i]增加1代替，唯一的不同是d[0]减少了1，而d[0]变成多少对最少操作次数没有影响！
同理d[i]减少1，可以通过d[0]增加1且d[i]减少1代替。
而每一个单独一个数增加/减少的操作，如果它像这样被代替了，那么d[0]就会增加1或者减少1。显然，有多少个单独增加/减少操作，d[0]就多了多少种可能。由前面已知，有max- min个单独增加/减少操作，那么d[0]有max - min + 1种不同的值。
#include "stdio.h"
#include "stdlib.h"
typedef long long LL;
int main() {
int n;
scanf("%d", &n);
LL d, pre, a;
LL positive = 0, negative = 0;
int i;
for (i = 0; i < n; i++) {
scanf("%lld", &a);
//求差分
//这里d没有使用数组，第i次循环的d表示d[i]
if (i) d = a - pre;
else d = a;
pre = a;
if (i) {
//计算除d[0]外正数之和与负数绝对值之和
d > 0 ? (positive += d) : (negative -= d);
}
}
LL max = positive > negative ? positive : negative;
LL min = positive > negative ? negative : positive;
//最少max次操作，max - min次单独增加/减少操作，d[0]有max - min + 1种不同的值
printf("%lld\n%lld", max, max - min + 1);
return 0;
}