1. 题目描述
2. 思路
很容易想到差分，将题目转化为（假设数组下标从 \(1\) 开始），最少的操作次数，使得差分数组 s[2] ~ s[n] = 0 的最少操作次数，s[1] 就是最后数组的元素值。
注意到
s[1]就是数组最后的值对求第二问的方案数很关键。
对于第一问，我们可以贪心的方式，在差分数组中，每次选取两个数，对一个数加一，对一个数减一。
但是这里需要注意两个边界情况，修改的数是 s[1] 和 s[n+1]。
为什么说是边界情况呢？先分析一下我们对原数组进行修改的几种情况：
- 修改的范围不包过头
[1]和尾[n]，那么，在差分数组中，[L] >= 2，[R] <= n - 修改的范围包括头，但是不包括尾，那么在差分数组中，
[L] == 1，[R] <= n - 修改的范围不包空头，但是包括尾，那么在差分数组中，
[L] >= 2，[R] == n + 1 - 修改的范围既包括头，又包括尾，那么在差分数组中，
[L] == 1，[R] == n + 1，但是修改整个数组毫无意义。
为什么要根据是否包括头和尾来划分修改的种类呢？相信你仔细看的话，应该可以从其对应于差分数组的修改看出端倪了！
当我们修改的范围从头开始，也就是包括头时，我们会修改 s[L]=s[1]，我们前面提到过， s[1] 就是数组最后的元素值，它直接影响着方案数！
当我们修改的范围包括尾时，我们会修改 s[R]==n+1，而这对我们差分数组毫无影响。
由于修改整个数组毫无意义，并且我们希望修改的 s[2]~s[n] 使得其元素值都为 0，而 s[1] 是多少不用管，所以，我们只关心 s[2]~s[n]
因此，下面的差分数组就代指 s[2]~s[n]
- 修改差分数组中的两个数
- 修改差分数组的一个数，并且会修改头
- 修改差分数组的一个数
我们发现，我们每次要么修改一个数，要么修改两个数（一个加一，一个减一），因此，贪心的话，第一问就解决了！
我们设差分数组(s[2]~s[n])中正数之和为 \(p\)，负数之和为 \(q\)
res1 = min(p, q) + abs(p - q);
其中，min(p,q) 定义修改 \(1\)，每次修改一个正数和一个负数，abs(p-q) 对定修改 \(2\)，每次修改一个数。
其实可以将上面的式子等价转换为： res1 = max(p,1);
对于第二问，我们前面不止一次提到过了，差分数组 s[1] 的值就是最后数组的元素，那么 s[1] 值可能的个数就是方案数。
我们前面对修改的划分也提到了，只有修改 \(2\) 会改变 s[1] 的值，那么方案数就取决于修改 \(2\) 的次数了！
由于修改 \(2\) 只会作用于 abs(p-q) 中，而修改 \(3\) 也可能作用于其中，所以 res2 = abs(p-q)+1
3. 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], s[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
long long p = 0, q = 0;
for(int i = 2; i <= n; i ++ )
{
s[i] = a[i] - a[i - 1];
if(s[i] > 0) p += s[i];
else if(s[i] < 0) q -= s[i];
else /* p == 0, ignore*/ ;
}
long long res1 = max(p, q);
int res2 = abs(p - q) + 1;
cout << res1 << endl << res2 << endl;
return 0;
}
4. 惨痛的教训
题目数据为 1e5，假设所有数都是正数，那么 res1 肯定爆 int