P4552 [Poetize6] IncDec Sequence
[Poetize6] IncDec Sequence
题目描述
给定一个长度为 n 的数列 a_1,a_2,...,a_n，每次可以选择一个区间[l,r]，使这个区间内的数都加 1 或者都减 1。
请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。
输入格式
第一行一个正整数 n
接下来 n 行,每行一个整数,第 i+1 行的整数表示 a_i。
输出格式
第一行输出最少操作次数
第二行输出最终能得到多少种结果
样例 #1
样例输入 #1
4
1
1
2
2
样例输出 #1
1
2
提示
对于 100% 的数据，n≤ 100000, 0 ≤ a_i ≤ 2^31。
分析
一个小时才学会差分= =太弱了，分享一下我学习差分的心得。非常详细 虽然很长但
看完保证明白，不明白可以私信问。
（本篇题解我们的数组的下标从1开始）差分的概念是b[1]=a[1]，b[i]=a[i]-a[i-1]，
简单来说就是两个数的差。b[1]一定是等于a[1]的，因为b[1]=a[1]-a[0]，而
a[0]=0,所以b[1]=a[1]。
了解了概念，我们看一下差分和原序列之间有什么关系
把序列a的区间[l,r]+d（或者说a[l]+d,a[l+1]+d,a[l+2]+d+....+a[r]+d的
话，那么这个序列a的差分序列b的变化就为b[l]+d,b[r+1]-d。为什么呢？举个例子
原序列a：1 3 4 2 1，其差分序列b:1 2 1 -2 -1
把区间[2,4]+2，得到的序列a应该是1 5 6 4 1
再看差分序列b，根据我们上面说的公式，a[2,4]+2应该等于b[2]+2,b[5]-2;
差分序列b变为：1 4 1 -2 -3
到底是不是这样呢？我们根据差分的概念倒推回去看看
由于b[1]=a[1]，且b[1]=1，所以a[1]=1;
b[2]=4，则a[2]-a[1]=b[2]=4;由于a[1]=1，得出a[2]=5;
b[3]=1，则a[3]-a[2]=1，由于a[2]=5，得出a[3]=6;
b[4]=-2,则a[4]-a[3]=-2，由于a[3]=6，得出a[4]=4;
b[5]=-3,则a[5]-a[4]=-3，由于a[4]=4，得出a[5]=1;
由差分序列倒推回来得到的原序列是1 5 6 4 1，完全符合我们之前得到的，说明这
个公式是正确的。
直观点说，原序列1 3 4 2 1，把区间[2,4]+2，得到的序列a是1 5 6 4 1
可以发现，a[2,4]中的差是不变的，因为他们同时加了一个数，变化的是a[l-1]和
a[l]之间的差以及a[r]和a[r+1]之间的差，这样一来，就很好推出这个差分序列公式
下面是这个公式的延伸
如果a[l,r]+1，则b[l]+1，b[r+1]-1;
如果a[l,r]-1，则b[l]-1，b[r+1]+1;
如果a[l,n]+1(l <= n - 1)，则b[l]+1，其余不变，因为b[n+1]已越界无意义
如果a[l,n]-1(l <= n - 1),则b[l]-1，其余不变，因为b[n+1]已越界无意义
下面看一下这个题该怎么做
要使得序列的数全部相等，其实就是让他们之间的差全为0，也就是差分序列的除了第
一项每一项都是0，为什么除了第一项呢，因为b[1]=a[1]-a[0]，而a[1]是开头的数
我们把问题转化成了让差分序列除第一项全等于0之后，继续思考
由于题目要求最少的步骤，我们可以考虑，如果差分序列里有一个正数和一个负数
（出现的顺序无所谓），那么我们优先对这个正数和负数进行操作，为什么呢？因为
我们有以下两个公式
如果a[l,r]+1，则b[l]+1，b[r+1]-1
如果a[l,r]-1，则b[l]-1，b[r+1]+1
正数-1，负数+1，这样相当于一步里作用了两步，比让正数一个个-1和让负数一个个
+1快多了
那么我们可以进行多少种这样的操作呢？
我们可以令差分序列里正数绝对值的总和为p，负数绝对值总和为q
可以进行这样一步顶两步的操作就是min（p，q），因为这种操作正数负数是一一配
对的，当少的那个先用完了，剩下的没有可以配对的了，只能一步步减或一步步加。
所以我们总共要进行的操作就为min（p，q）+abs（p-q），也就是max（p，q）
第一问完成，看第二问
保证最少次数的前提下，最终得到的数列有多少种？
得到的数列有多少种，其实就是问的b[1]可以有多少种
我们上述所有操作是与b[1]无关的，因为我们的目标是让除了b[1]以外的项变0，所
以我们上述的操作没有考虑到b[1]，b[1]怎么变，与我们求出的最小步骤无关
那么，我们怎么知道b[1]有几种呢？很简单，其实就是看看有几种一步步减或一步步
加的操作数，因为我们一步步加的时候（假设我们现在的操作对象下标为i），
可以这样操作，b[1]-1,b[i]+1
一步步减的时候可以这样操作，b[1]+1,b[i]-1
（注意，一个差分序列里一步步操作的时候只可能一步步加或一步步减，不可能一步
步加和一步步减同时存在）
所以说，有几步一步步的操作就有几种情况+1，为什么+1呢，因为这个b[1]本身就有
一个值啊！就算你不对他进行任何操作，它自己也有一种情况。
一加一减（也就是我们所说的一步顶两步的操作）操作数为min（p，q）
那么一步步的操作数就为max（p，q）-min（p，q）=abs（p，q）
完结撒花
提交答案
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n,c,p,q,a[100010];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(int i=2;i<=n;i++)
{
c=a[i]-a[i-1];
if(c>0)
{
p+=c;//p为正数绝对值的总和
}
else
q-=c;//q为负数绝对值总和
}
LL ans1=max(p,q);//ans1为最少操作次数
LL ans2=abs(p-q)+1;//ans2为最终能得到多少种结果
cout<<ans1<<endl<<ans2;
return 0;
}