B. Mark the Dust Sweeper（思维）

题目

题意

给定n个数，可以执行以下操作
选择下标i<j，且a[i],a[i+1],…a[j-1]都大于0；令a[i]=a[i]-1，a[j]=a[j]+1。

问最少需要多少次上述操作，才能将a[1],a[2],…,a[n-1]都置为0。

思路

要让a[1],a[2],…,a[n-1]都置为0，需要将它们都搬运到a[n]上，因此答案为a[1]+a[2]+…+a[n-1]。又由于搬运过程，要求中途的元素都大于0，因此，遇到0值时，且它前面还有非0元素，则说明需要至少填充一个元素到该位置。
补完桥，才能过河。

结合代码理解。

代码

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int maxn = 200010;
const int mod = 1e9 + 7;

int n; 
int a[maxn];
void solve() {
    
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
    
		scanf("%d", &a[i]);
	}
	ll res = 0;
	bool all_zero = true;
	for (int i = 0; i < n - 1; ++i) {
    
		res += a[i];
		if (!a[i]) {
    
			if (!all_zero) {
    
				++res;
			}
		} else {
    
			all_zero = false;
		}
	}
	printf("%lld\n", res);
	
}

int main() {
    
	int t;
	scanf("%d", &t);
	while (t--) {
    
		solve();
	}
}