自动搬运

查看原文

来自洛谷，原作者为

	SmallTownKid 大学生

搬运于2025-08-24 22:01:16，当前版本为作者最后更新于2020-05-12 16:09:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一个小时才学会差分= =太弱了，分享一下我学习差分的心得。非常详细 虽然很长但

看完保证明白，不明白可以私信问。

（本篇题解我们的数组的下标从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;
}