ACW100
题意
给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
输入格式
第一行输入正整数n。
接下来n行，每行输入一个整数，第i+1行的整数代表 ai。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
```0≤ai<2147483648```
## 输入样例：
4 1 1 2 2
1
2
3
## 输出样例：
1 2
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
## 思路
一看到这个题是区间加常数,所以优先想到采用差分数组.(命名为```p[]```)
先讨论最少需要多少次操作才能让数列中所有数都一样,我们发现,**```p[1]```这一项并没有意义**,因为其表示a1的大小(此处假设a0始终为0),而且区间都加1和区间都减1恰好是对应了 ```p[l]+1,p[r+1]-1``` 和 ```p[l]-1,p[r+1]+1```这两种情况.我们最终的目的是让```p[2]~p[n]``` 全部变成0,
还能发现,p[n+1]可以作为一个仓库,任何数都可以通过和p[n+1]操作来归零,负数可以通过操作1来归零,正数可以通过操作2来归零,但是我们发现**正数和负数归零貌似更划算一些** ,假设正数之和为s1,负数的**绝对值**之和是s2,那么最后会剩下``|s1-s2|`` ,**我们可以通过```p[1]和p[n+1]``` 来处理他们,然后我们又发现p[n+1]并不会对数组最终的值造成影响,但是!如果对p[1]操作的话,会改变整个数组的最终值!**
综上所述:最少的操作次数是```|s1-s2|(剩余数和p[1]或者p[n+1]处理) + min{s1,s2}(正负数互相处理) ```
而最终得到的数列的种类数其实就是```|s1-s2|+1```,因为所谓数列的总类数也就是p[1]的取值,而p[1]可能会进行```[0,|s1-s2|]```种**相同操作**(因为最后要么只剩下正的没处理,要么只剩下负的没处理),所以最后数列的总类数是```|s1-s2|+1```.
## AC代码
```c
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#define ll long long
#define LL ll
using namespace std;
int a[100100];
int p[100100];
ll myAbs(ll x) {
if (x >= 0ll) {
return x;
}
return -x;
}
int main() {
int n;
while (cin >> n) {
a[0] = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
p[i] = a[i] - a[i - 1];
}
ll s1 = 0ll;
ll s2 = 0ll;
for (int i = 2; i <= n; ++i) {
if (p[i] > 0) {
s1 += p[i];
} else {
s2 += -p[i];
}
}
cout << myAbs(s1 - s2) + min(s1, s2) << endl;
cout << myAbs(s1 - s2) + 1 << endl; // 其实就是a1的所有可能取值
}
return 0;
}
