本文主要是介绍寒假打卡-算法-差分--例题AcWing 100. IncDec序列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

差分数组：

差分数组就是前缀的逆过程；

a[1],a[2],.…a[n]
b[i]=a[i]-a[i-1],b[1]=a[1]

那么a[i]就是b[i]的前缀和数组；

证明过程如下：

a[i]=b[1]+b[2]+.…+b[i]
    =a[1]+a[2]-a[1]+a[3]-a[2]+.…+a[i]-a[i-1]
    =a[i]

性质:

1. 差分序列求前缀和可得原序列
2. 将原序列区间[L,R]中全部的元素+1，可以转化操作为差分序列L处+1，R+1处-1
3. 按照性质2得到，每次修改原序列一个区间+1,那么差分序列修改处增加的和减少的相同

作用:

在o(1)的时间内，在一段[l,r]的区间内同时加上一个常数c；

方法：

b[l]+=c,b[r+1]−=c；

这样下来就在区间[l,r]上同时加了一个常数c;

例题引用100. 增减序列 - AcWing题库

给定一个长度为 nn 的数列 a1,a2,…,ana1,a2,…,an，每次可以选择一个区间 [l,r][l,r]，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式

第一行输入正整数 nn。

接下来 nn 行，每行输入一个整数，第 i+1i+1 行的整数代表 aiai。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

0<n≤1050<n≤105,
0≤ai<21474836480≤ai<2147483648

输入样例：

4
1
1
2
2

输出样例：

1
2

本题题解:

我们需要让a[i[数组所有的数字都相等，每次操作只能是在区间内加一或者减一，那么显然这道题需要用到的就是差分数组，我们只需要将差分数组的所有数都变成0就好了；

我们假设差分数组内所有的的正数的和为pos,负数的和为neg那么显然会有一种情况发生就是abs(neg)!=pos;

这种情况我们只需要将多余的数字和b[i]去加减便可以将这个数字减或者加为0；

那么有如下公式:

ans1=min(pos,neg)+abs(pos−neg)
ans2=abs(pos−neg)+1

ac代码如下:

#include<iostream>
#include<cmath>
using namespace std;
const int N=100010;
int num[N];
int n;
int main()
{
	cin>>n;
	long long pos=0,neg=0;
	for(int i=0;i<n;i++)
	{
		cin>>num[i];
	}
	for(int i=n-1;i>0;i--)
	{
		num[i]-=num[i-1];
		if(num[i]<0)	neg-=num[i];
		else	pos+=num[i];
	}
	cout<<min(pos,neg)+abs(pos-neg)<<endl<<abs(pos-neg)+1<<endl;
	return 0;
}

这篇关于寒假打卡-算法-差分--例题AcWing 100. IncDec序列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！