题解 P4552 【[Poetize6] IncDec Sequence】

一个小时才学会差分= =太弱了，分享一下我学习差分的心得。非常详细 虽然很长但 看完保证明白，不明白可以私信问。 （本篇题解我们的数组的下标从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; } else q-=c; } LL ans1=max(p,q); LL ans2=abs(p-q)+1; cout<<ans1<<endl<<ans2; return 0; }