本文共 1552 字，大约阅读时间需要 5 分钟。

题意

给定一个数组,每次可以把一个前缀的数全部减一,或者把一个后缀全部减一

问最后有没有可能让所有数都变成$0$

代劳们的神仙差分思路

考虑差分数组$ans[i]$.如果所有数变成零,那么最后$ans$一定也是零

对于操作一,就是$ans[1]--,ans[i+1]++$

对于操作二,就是$ans[i]--,ans[n+1]++$

那么观察到$ans[1]$只会一直减小

而后续如果想让某个$ans[i]$从负数变成零必然要用操作一

后续如果要让某个$ans[i]$从正数变成零用操作二就可以了

而且操作二不管让$ans[n+1]$变成多少都无所谓

因为只要保证$[1,n]$的差分数组为零都是相同的数,那肯定能变成全是零

所以只需要关心$ans[1]$是不是足以让后面的所有负的$ans[i]$变成零

#include "iostream"using namespace std;const int maxn = 2e6+10;int a[maxn],n,ans[maxn];int main(){
   	int t; cin >> t;	while( t-- )	{
   		cin >> n;		for(int i=1;i<=n;i++)	cin >> a[i], ans[i] = a[i]-a[i-1];		for(int i=2;i<=n;i++)			if( ans[i]<0 )	ans[1]+=ans[i];		if( ans[1]>=0 )	cout << "YES\n";		else	cout << "NO\n";	}}

我的做法贪心

宗旨是先只考虑操作一如何操作最优

只要通过操作一把序列变成不递减,说明可以只通过操作二来完成.

比如11 7 9

第一个数肯定操作了$11$次,然后到第二个数,现在衰减到$7$次,但是都变成了零

但是第三个数怎么办??已经不能让它等于0了

贪心策略是让它在大于等于前面数字的前提下尽量小

这个应该很好理解,大于前面的话无法通过操作二来消除

尽量小则是让操作二更容易消除

$基于这个贪心法则,甚至可以构造出最优的操作顺序$

因为这样操作最后序列变成不递减的了,可以只通过操作二来实现.

#include "iostream"using namespace std;const int maxn = 2e6+10;int a[maxn],n;int main(){
   	int t; cin >> t;	while( t-- )	{
   		cin >> n;		for(int i=1;i<=n;i++)	cin >> a[i];		int ci = a[1], flag = 0;//初始操作次数是a[1]		a[1] = 0;		for(int i=2;i<=n;i++)		{
   			if( a[i]

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110144017 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！