【蓝桥每日一题]-前缀和与差分（保姆级教程 篇2）#差分序列

昨天讲的概念和模板，今天讲一个差分序列的好题(好好体会里面的优化思想)：

目录

题目：

思路： 

---

         

       

题目：

手动打出样例哈
输入：                        输出：
4                                    2
3                                    13
-2 -2 -2                          36
3                                    33
10 4 7
4 
4 -4 4 -4
5
1 -2 3 -4 5

        

思路： 

先捋一下题意：给定长n的序列现有三种操作：问至少经过多少次操作才能把所有数都变成0。一共t次询问！

操作1，选一个数ai把1~i的数都减少1
操作2，选一个数ai把i~n的数都减少1
操作3，每个数都增加1

      

很明显要用差分序列来做，不过怎么使用差分序列很考思维和技巧

    
操作1：把dif[i+1]+1，dif[1]-1
操作2：把dif[i]-1
操作3：把dif[1]+1

我们只需要对差分序列不断进行三个操作，直到变成全0即可

      
举个例子：原数列：1 -2 3 -4 5    对应制造差分：1，-3，5，-7，9
不难发现对于大于0的5，9需要减少，那就是执行操作2；

对于小于0的-3，-7执行操作1即可；

然后只剩下dif[1]了，最后执行操作3就行了

      

#include 
using namespace std;
typedef long long ll;
const int S=1<<18;
int a[S];
ll ans,dif[S];
void solve(){
	ans=0;
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dif[i]=a[i]-a[i-1];//制造差分序列
	}
	for(int i=2;i<=n;i++){
		if(dif[i]>0)ans+=dif[i];//执行操作2
		else {
			int ab=-dif[i];
			ans+=ab;//执行操作1
			dif[1]-=ab;
		}
	}
	ans+=abs(dif[1]);//执行操作3
	cout<'\n';
}
int main(){
	int t;cin>>t;
	while(t--) solve();
	return 0;
}

综上：你是不是也发现我之前说的，“差分序列多于用数据的多次变动” 的意思了吧