我估计不少彦祖(包括祖贤)没太理解后面p,q的意思,如果视频没看明白,可以赏脸来看看我的解释,这里我先上代码:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 100010;
LL n;
LL a[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
//for (int i = 1; i <= n; i++)cout << a[i] << " ";
for (int i = n; i > 1; i--)a[i] -= a[i - 1];
//for (int i = 1; i <= n; i++)cout << a[i] << " ";
//cout << endl;
LL p, q;
p = q = 0;
for (int i = 2; i <= n; i++){
if (a[i] > 0){
p += a[i];
}
else q -= a[i];
}
cout << min(p, q) + abs(p - q) << endl;
cout << abs(p - q) + 1 << endl;
return 0;
}
我们用题目上的例子来看一下:
a[] = 1 1 2 2
b[] = 1 0 1 0
我们首先对差分数组b[]中的正负数进行遍历,因为我们最终的目的就是把b[1…n]全变成0
p = b[]中所有大于0的和,q = b[]中所有小于0的和(等于0无所谓,因为加0原数不变)
我们知道的是想要在原数组中对a[l~r]的数字进行加减x,对应差分数组的操作就是b[l] + x, b[r + 1] - x,使其除了b[1]都是0
那么我们的思路就是找到差分数组中的正负数对,因为这样了话前面b[l] + x直接能找到这个配对的b[r + 1] - x
此时操作后p就是所有正数和,q就是所有负数和
对应题目例子中就是:
b[3] = 1 –> p += 1
最后得到p = 1, q = 0
min(p, q)指的就是找到的正负数对,因为匹配的对数一定是p和q小的那一个
此时要知道,p和q不一定相等,肯定会有多出来的,可能正数多也可能负数多
因此abs(p - q)就是多出来的那一些,而这些还需要操作把它们变成0
最后,总操作数就是min(p, q) + abs(p - q)了
而种类数就是abs(p - q)了,为什么呢?
种类数其实就是b[1] (a[1])的种类数,因为我们自始至终都没有动过b[1],都是围绕b[2~n]来操作的,让原数组其他数和a[1]一样
只有最后我们找到abs(p - q)这一堆多于出来没数匹配的,它们需要通过b[1]的改变来调整,也就是y总说的方法2,3
因此种类数九数abs(p - q) + 1,后面这个1是原本b1的那个初始情况。