因为到为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+;
int a[maxx];
int main(){
int n,d;
int maxx=;
int minn=;
scanf("%d%d",&n,&d);
int flag=;
int cnt=;
for (int i=;i<=n;i++){
scanf("%d",&a[i]);
if (a[i]==){
///代表要进行检查
if (maxx<){ ///如果最大值小于0 那么必须要充钱
cnt++;
///充钱后,充钱的数目可能是0,那么最小值变成了0
///充钱后,最大钱的数目为d
minn=;
maxx=d;
}else {
///但是如果当前最大值是小于等于d的
///为了满足条件,最小值至少也是满足>=0的
minn=max(minn,);
}
}else {
maxx+=a[i];
minn+=a[i];
maxx=min(maxx,d);
}
if (minn>d){
flag=;
}
}
if (flag)printf("-1\n");
else printf("%d\n",cnt);
return ;
}

最新文章

  1. (转)Spring中@Async用法总结
  2. 网络编程(一):用C#下载网络文件的2种方法
  3. fir.im Weekly - 如何打造真正的工程师文化
  4. [转]hibernate在eclipse的逆向工程生成hbm.xml和bean类
  5. BZOJ4527: K-D-Sequence 线段树
  6. 希望各位博友能对我的自我介绍提出意见(要面试IBM的应用开发工程师,本科应届生一枚)
  7. JQuery判断数组中是否包含某个元素$.inArray(&quot;js&quot;, arr);
  8. 如何创建和发布.asmx Web Service
  9. ZigBee profile
  10. Silverlight中嵌套html、swf、pdf
  11. python和django的一些小技巧(locals()...)
  12. Alice&#39;s Chance
  13. 数位dp初探
  14. Python基础__函数
  15. Java实现将任何编码方式的txt文件以UTF-8编码方式转存
  16. Cas 服务器 下载、编译及部署
  17. BZOJ5317 JSOI2018部落战争(凸包)
  18. Ubuntu 1604配置安装mysql8.0
  19. 《LeetBook》leetcode题解(17):Letter Combinations of a Phone Number[M]
  20. HDU3853 LOOPS 期望DP 简单

热门文章

  1. javax.el.PropertyNotFoundException: Property &#39;studentAge&#39; not found on type com.hs.model.StudentModel
  2. springmvc报404错误No mapping found for HTTP request with URI [/mavenSpringmvc/requesttest] in DispatcherServlet with name &#39;spring&#39;
  3. GIT → 05:Git命令行操作
  4. Mac OS 安装 独立的asio库
  5. vue 使用 element ui动态添加表单
  6. 阿里云杨敬宇:5G时代,边缘计算将发挥更大价值
  7. ML面试1000题系列(21-30)
  8. linux开发脚本自动部署及监控
  9. uni-app官方教程学习手记
  10. Mybatis中example类的使用