今日题解------codeforce 893d

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

如果被查到信用卡里的钱小于零，那你就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<bits/stdc++.h>

#define de(x) cout<<#x<<"="<<x<<endl;

#define dd(x) cout<<#x<<"="<<x<<" ";

#define rep(i,a,b) for(int i=a;i<(b);++i)

#define repd(i,a,b) for(int i=a;i>=(b);--i)

#define mt(a,b) memset(a,b,sizeof(a))

#define fi first

#define se second

#define inf 0x7f

#define pii pair<int,int>

#define pdd pair<double,double>

#define pdi pair<double,int>

#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+;

const int maxn = 1e5+;

const double EPS = 1e-;

using namespace std;

int gcd(int a,int b){

    return b==?a:gcd(b,a%b);

}

ll a[maxn];

int main()

{

    int n;

    ll d;

    scanf("%d%lld",&n,&d);

    rep(i,,n){

        scanf("%lld",&a[i]);

    }

    ll sum = ;

    int ans = ;

    int low = ,top = ;

    rep(i,,n){

        if(a[i]){

            low+=a[i];top+=a[i];

            if(low>d) return printf("-1\n"),;

            if(top>d) top = d;

        }else {

            low = max(low,);

            if(top<) top = d,ans++;

        }

    }

    printf("%d\n",ans);

    return ;

}

巴特西

今日题解------codeforce 893d

最新文章

热门文章