代码实现:此题主要是要想到,我们可以发现,因为前面的值减少,后面的值增加,
所以对于正数i,我们让a[i]减少,a[i + 1]增加。 因为a[i + 1]如果为正数,增加之后,再按照这个思路减少,不花钱。如果为负数,则刚好。
如果a[i]还是为负数。那么这就要花钱,因为前面已经为0,必须队i进行加法,而后面进行减少。那么对哪个进行减法呢?花了钱的减法很珍贵。
1.放到后面的正数上,本来加法减就不要钱,而且加法进行减,可以让负数进行增,还不要钱。所以不可能放正数上。
2.放到后面的负数上,本来负数进行增加就要钱,你还要减,那花的钱更多。
所以放到最后面。因为按照这样的 *** 作。
a[i - 1], a[i]中1 ~ a[i - 2]都变为了0.
那么a[i - 1] + a[i]为0.
所以最后算a[i - 1]进行 *** 作所需要的钱就可以了。
# includeusing namespace std; const int N = 1e5 + 10; int n; int t; long long a[N]; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i = 1 ; i <= n ; i++) { scanf("%lld",&a[i]); } long long ans = 0; for(int i = 1 ; i <= n ; i++) { if(a[i] == 0) { continue; } if(a[i] > 0) // 那么a[i]减 , a[i + 1]增加,哪怕a[i + 1]为增加,那么继续,反正前减后增不要钱 { a[i + 1] += a[i]; } else // a[i] < 0 那么a[i]增加, 让a[n]减少 , 因为后面如果为正数,那么本来减少就不要钱,不用浪费这次花钱的机会,而负数减少太亏了,所以让最后的a[n]减少,最后一定只剩下a[n - 1]和a[n] { ans -= a[i]; a[n] += a[i]; } } printf("%lldn",ans); } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)