博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
今日题解------codeforce 893d
阅读量:6828 次
发布时间:2019-06-26

本文共 1510 字,大约阅读时间需要 5 分钟。

题意:给你一个数列,小于零表示表示信用卡里取出钱,大于零表示信用卡里存钱,等于零表示要查询信用卡,

如果被查到信用卡里的钱小于零,那你就GG,或者在任何时候你的信用卡里的钱大于d的话(不需要找ai等于的时候)你也GG,

然后你可以在任意一天的白天去存钱(任意数量),问你最少去几次银行,如无法满足就输出负一

我的题解:

我们发现如果信用卡里的钱是负数的话,其实我们可在那天去存钱,因为是可以存任意数量的钱,所以你肯定不用担心你的钱会是负数,所以

我们只要让信用卡里的钱不超过d就行了;

我先来说说我一开始wa的思路吧,我就是一直加上ai然后再sum>d的话就是-1,不然的话就ans++,然后把sum更新成零,但是你会发现,你的对于负一

的情况是对的,但是你不能保证去的次数最少。。(比如cf的第7组数据)

然后我看了题解之后,你会发现你每次经过零 的时候,你的接下来的金额是在一个范围内(max(low,0),min(d,top))内,然后你在后面的话,可以在这个区间里面

任意的取,如果low>d的话,显然这是-1的情况,那如果经过0之后,low肯定不能小于零,所以如果她小于零的话,就要更新low,还有在任意的时刻,你的top都不能超过d

所以每次top>d的时候,我们就把它变成d。

代码;

#include
#define de(x) cout<<#x<<"="<
<
=(b);--i)#define mt(a,b) memset(a,b,sizeof(a))#define fi first#define se second#define inf 0x7f#define pii pair
#define pdd pair
#define pdi pair
#define mp(u,v) make_pair(u,v)#define sz(a) a.size()#define ull unsigned long long#define ll long long#define pb push_back#define PI acos(-1.0)const int mod = 1e9+7;const int maxn = 1e5+5;const double EPS = 1e-6;using namespace std;int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}ll a[maxn];int main(){ int n; ll d; scanf("%d%lld",&n,&d); rep(i,0,n){ scanf("%lld",&a[i]); } ll sum = 0; int ans = 0; int low = 0,top = 0; rep(i,0,n){ if(a[i]){ low+=a[i];top+=a[i]; if(low>d) return printf("-1\n"),0; if(top>d) top = d; }else { low = max(low,0); if(top<0) top = d,ans++; } } printf("%d\n",ans); return 0;}

 

转载于:https://www.cnblogs.com/chinacwj/p/7987067.html

你可能感兴趣的文章
UIView 进行各种动画展示及其用法解释
查看>>
公布2012年5月赛CSDN算法达人赛试题及参考答案
查看>>
Mysql ON子句和USING子句
查看>>
linux杂谈
查看>>
类型、值和变量
查看>>
UIImage+Scale
查看>>
Linux sed 替换第一次出现的字符串
查看>>
windows 下VLC播放器应用之二------LIBVLC API解析
查看>>
用户权限管理,LINQ去除它的重复菜单项
查看>>
php mysql 导出excel
查看>>
android 日期选择器(DatePicker)学习与应用 (转)
查看>>
web页面常用功能js实现
查看>>
30天学会 MooTools 教学(1): 认识MooTools
查看>>
【转载】iphone IOS plist文件
查看>>
linux下多进程、多线程编程
查看>>
jmeter最简单使用
查看>>
Android开发中SharedPreferences的应用
查看>>
Forward框架的逆袭:解析Forward+渲染
查看>>
转 互斥锁和条件变量
查看>>
java打包jar的入口问题解决
查看>>