题意:给你一个数列,小于零表示表示信用卡里取出钱,大于零表示信用卡里存钱,等于零表示要查询信用卡,
如果被查到信用卡里的钱小于零,那你就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;}