题意:有一个长度为\(n\)的序列,可以任意取\(k(1\le k\le n)\),对序列前\(k\)项或者后\(k\)减\(1\),可以进行任意次操作,问是否可以使所有元素都变成\(0\).
题解:贪心,我们优先考虑从左边减,如果当前项比后一项大\(a_i>a_{i+1}\),那么我们一定可以从左边减,使得这个区间变为\(0\),否则,光从左边减是不能使后一项元素变为\(0\)的,此时我们就要从右边减,即某尾到这项这段区间减去差值\(a_{i+1}-a_i\),我们可以直接累加这些差值,如果遍历到某一项比差值之和小的话,就说明不满足条件.
-
代码:
int t;
int n;
int a[N]; int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
int res=0; bool flag=true; for(int i=1;i<=n;++i){
if(res>a[i]){
flag=false;
break;
}
if(a[i]<a[i+1]) res+=a[i+1]-a[i];
} if(flag) cout<<"YES\n";
else cout<<"NO\n";
} return 0;
}