因为到为0的点,充钱的范围都是不确定的,我们维护一个满足条件的最小值以及满足条件的最大值。
当min>d时,代表已经满足条件限制了
当a[ i ] = 0 并且 max<0,代表需要充钱,充钱能够保证当前 minn=0 maxx = d
其他情况则对minn, maxx相应的增加和减少进行操作就可以了
#include<bits/stdc++.h> using namespace std; const int maxx = 2e5+6; int a[maxx]; int main(){ int n,d; int maxx=0; int minn=0; scanf("%d%d",&n,&d); int flag=0; int cnt=0; for (int i=1;i<=n;i++){ scanf("%d",&a[i]); if (a[i]==0){ ///代表要进行检查 if (maxx<0){ ///如果最大值小于0 那么必须要充钱 cnt++; ///充钱后,充钱的数目可能是0,那么最小值变成了0 ///充钱后,最大钱的数目为d minn=0; maxx=d; }else { ///但是如果当前最大值是小于等于d的 ///为了满足条件,最小值至少也是满足>=0的 minn=max(minn,0); } }else { maxx+=a[i]; minn+=a[i]; maxx=min(maxx,d); } if (minn>d){ flag=1; } } if (flag)printf("-1\n"); else printf("%d\n",cnt); return 0; }