牛客寒假训练营5 C

anon的私货

链接

大意: 要求除全 0 连续子数组外的每个连续子数组的平均数都大于等于 1,0最多有多少个

分析: 证明太菜了，不会，贪心的策略大概就是左右两边加起来0的个数不超过x-1，能放左边尽量放左边

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int n;
int a[100050];
i64 ans=0;
int main(){
	ios;
	cin>>n;
	for(int i = 1;i<=n;++i) cin>>a[i];
	a[0]=a[n+1]=0x3f3f3f3f;
	for(int i = 0;i<=n;++i){
		int x = min(a[i]-1,a[i+1]-1);
		a[i]-=x;
		a[i+1]-=x;
		ans+=x;
	}
	cout<<ans;
	return 0;
}