前缀和差分

目录

第一题：100. 增减序列 - AcWing题库

第二题：​​​​​​101. 最高的牛 - AcWing题库

---

今天主要说一说差分吧，之前一直知道差分但感觉好像没什么用，但其实挺好用，如果可以的话，能大大降低复杂度，主要就是把区间的统一 *** 作变化到区间端点上，假如把一个区间同时加上或者减去d，只需要把原序列的差分数组求出来c[l]+=d,c[r+1]-=d，很妙。原序列的差分数组和差分数组的前缀和是等价的，设原数组是a，差分数组是b，那b[i]=a[i]-a[i-1]，这个式子有个隐含的条件就是a[1]==b[1]，然后开始进行差分，通俗的来说差分数组就是后一个数-前一个数，然后第一个数字相同，就这个，下面来看看题：

第一题：100. 增减序列 - AcWing题库

题意就是给你一个序列，然后选择任意的区间进行+1或者-1，最终得到这个序列完全一样，问最少 *** 作多少次，还有问这样的序列能有多少种？（数据范围1e5）

题解：任意区间 *** 作，数据范围那么大，暴力肯定不行，很容易能想到差分，我想了想差分好像没有头绪，感觉乱糟糟的。后来看题解才明白要分情况讨论：

刚刚有一点很重要，就是原数组和差分数组的第一个数是相同的，就借助这个性质来分类，还有差分数组的前缀和是原数组，所以希望b2,b3...bn都是0，然后原序列就是n个b1，这是最优解

分类讨论：（这里设p为正数的和，q为负数绝对值的和）

①2<=i,j<=n-1 那这里的操作次数就是min(p,q)，//这里的点要注意，可以选择任意区间，我刚开始想的是正数的个数和负数的个数，其实要看总和，任意区间都可以选，最好的情况是正数的和==负数的绝对值的和，那在第一种情况就可以得到相等的数组

②（前缀）i==1，2<=j<=n-1,这里就是直接|p-q|，第一个情况剩下来的，要从第一个数进行改变了

③（后缀），同理2

④全部（无意义）

所以综上所述，最少的 *** 作次数等于min(p,q)+|p-q|==max(p,q)

不同的种类数：|p-q|+1

代码：

#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N],b[N];
int main(){
	ll n;
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];
	ll p=0,q=0;
	for(int i=2;i<=n;i++)
	{
		if(b[i]>0) p+=b[i];
		else if(b[i]<0) q-=b[i];
	}
	cout< 
第二题：​​​​​​101. 最高的牛 - AcWing题库 
题意就是给你一个n头牛中最高的牛的编号和高度和m对关系，这两头牛能相互看见，中间的牛必须不高于这两头牛，求每头牛最高可能是多高
 
这个题我想了一下，思路和题解是一样的，就是最高的牛和能看见最远的地方肯定都是h，往里面-1，但是不太会写出来，但其实很简单啦
 
设c数组是改变数组，就是在每头牛的基础上改变了多少，设d为c数组的差分数组
 
c的初始都是0，（当然最高的那头肯定一直都是0），就刚刚的思路，两个区间l,r，c[l+1]--,c[r-1]--自己手动模拟一下（我就不配图了QAQ），因为c是一段区间上的 *** 作，所以d只需要在两个端点上 *** 作就好（这里要注意，可能会有重复关系，还需要判断一下，还有给的关系的区间并不是l 
#include
#include
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/1498866.html