EC round 33 D. Credit Card 贪心
2024-10-08 01:16:11
因为到为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 ;
}
最新文章
- (转)Spring中@Async用法总结
- 网络编程(一):用C#下载网络文件的2种方法
- fir.im Weekly - 如何打造真正的工程师文化
- [转]hibernate在eclipse的逆向工程生成hbm.xml和bean类
- BZOJ4527: K-D-Sequence 线段树
- 希望各位博友能对我的自我介绍提出意见(要面试IBM的应用开发工程师,本科应届生一枚)
- JQuery判断数组中是否包含某个元素$.inArray(";js";, arr);
- 如何创建和发布.asmx Web Service
- ZigBee profile
- Silverlight中嵌套html、swf、pdf
- python和django的一些小技巧(locals()...)
- Alice&#39;s Chance
- 数位dp初探
- Python基础__函数
- Java实现将任何编码方式的txt文件以UTF-8编码方式转存
- Cas 服务器 下载、编译及部署
- BZOJ5317 JSOI2018部落战争(凸包)
- Ubuntu 1604配置安装mysql8.0
- 《LeetBook》leetcode题解(17):Letter Combinations of a Phone Number[M]
- HDU3853 LOOPS 期望DP 简单
热门文章
- javax.el.PropertyNotFoundException: Property &#39;studentAge&#39; not found on type com.hs.model.StudentModel
- springmvc报404错误No mapping found for HTTP request with URI [/mavenSpringmvc/requesttest] in DispatcherServlet with name &#39;spring&#39;
- GIT → 05:Git命令行操作
- Mac OS 安装 独立的asio库
- vue 使用 element ui动态添加表单
- 阿里云杨敬宇:5G时代,边缘计算将发挥更大价值
- ML面试1000题系列(21-30)
- linux开发脚本自动部署及监控
- uni-app官方教程学习手记
- Mybatis中example类的使用