基础算法----前缀和 and 差分

本文主要是介绍基础算法----前缀和 and 差分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前缀和

f[i] [j]为前缀和数组，a[i] [j]为原数组

f[i] [j] = f[i-1] [j] + f[i] [j-1] - f[i-1] [j-1] + a[i] [j]

算区间前缀和，画个图推公式

差分

原数组a[i], 差分数组f[i] = f[i] - f[i-1], f[1] = a[1]

性质1：差分数组的前缀和序列为a, 即差分数组前缀和s[i], s[i] = a[i];

性质2：给原数组a区间在[l, r]各加d ，f[l] += d, f[r+1] -= d(减d则是f[l] -= d, f[r+1] += d), f其余不变---->当对原数组进行区间操作时，可以转化成对差分数组的单店操作

例：

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

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

输入格式

第一行输入正整数 n。

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

输出格式

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

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

数据范围

0<n≤105
0≤ai<2147483648

输入样例：

4
1
1
2
2

输出样例：

1
2

已知差分数组性质2，每次可以令差分数组中的一个数+1，另一个数-1,目的是将差分数组b[2] - b[n]都变为0

先求出差分数组b，令psum为b中的正数和，nsum为b中的负数和的绝对值，之后可以先进行min(psum, nsum)次，进行相平，之后还差|psum - nsum|下相平，可以再把这些数字和b1或b[n-1]进行相平(b[1]与b[n+1]的值不影响结果)，因此总操作次数为min(psum, nsum) + |psum - nsum|, 而总结果种类可以为0到|psum - nsum|任意一种，因此总结果种数为|psum - nsum| + 1

代码示例：

ll a[100005];
ll b[100005];
ll n, nsum, psum;
ll ans;
ll cnt;

int main ()
{	
	cin >> n;
	For(i, 1, n) cin >> a[i];
	b[1] = a[1];
	For(i, 2, n) 
	{
		b[i] = a[i] - a[i-1];
		if(b[i] < 0) nsum += b[i];
		else psum += b[i];
	}
	nsum *= -1;

	ll tm = psum - nsum;
	if(tm < 0) tm *= -1;
	ans += min(psum, nsum);
	ans += tm;
   
	cnt = tm + 1;
	cout << ans << endl << cnt << endl;
	return 0;
}	

这篇关于基础算法----前缀和 and 差分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！