CodeForces - 893D 贪心

时间：2020-12-13 03:04:44

http://codeforces.com/problemset/problem/893/D

题意

Recenlty Luba有一张信用卡可用，一开始金额为0，每天早上可以去充任意数量的钱。到了晚上，银行会对信用卡进行一次操作，操作有三种操作。 1.如果a[i]>0，银行会给卡充入a[i]元。 2.如果a[i]<0 银行从卡中扣除a[i]元。 3.如果a[i]=0 银行会查询卡里的金额。 有两条规则，如果违背信用卡就会被冻结。 1.信用卡里的金额不能大于d。 2.当银行查询卡里的金额时，金额不能为负。 Recenlty Luba想知道最少去充多少次钱，可以使她在接下来的n天里信用卡不被冻结。

奥妙重重贪心。

用一个high和一个low来表示目前所有可能的钱的状态，开始不存钱的时候是(0,0)，如果遇到a[i] != 0,就将low和high同时加上a[i],但是由于high是不能超过d的，超过d的部分自动忽略掉，high还是d。

但是如果一旦low超过了d，表示当前无论如何都要超过d的钱，返回-1

当遇到查询的时候，如果high仍然大于0，说明她还有一种不充钱的方法，只要把low变成max(low,0)就可以了，因为这种情况下钱一定不为负数，如果high小于0，就不得不充钱了，将区间初始化为low = 0,high = K即可；

#include <map>

#include <set>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

const int MAXBUF=;char buf[MAXBUF],*ps=buf,*pe=buf+;

inline bool isdigit(const char& n) {return (n>=''&&n<='');}

inline void rnext(){if(++ps==pe)pe=(ps=buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);}

template <class T> inline bool in(T &ans){

#ifdef VSCode

ans=;T f=;register char c;

do{c=getchar();if ('-'==c)f=-;}while(!isdigit(c)&&c!=EOF);

if(c==EOF)return false;do{ans=(ans<<)+(ans<<)+c-;

c=getchar();}while(isdigit(c)&&c!=EOF);ans*=f;return true;

#endif

#ifndef VSCode

ans =;T f=;if(ps==pe)return false;do{rnext();if('-'==*ps)f=-;}

while(!isdigit(*ps)&&ps!=pe);if(ps==pe)return false;do{ans=(ans<<)+(ans<<)+*ps-;

rnext();}while(isdigit(*ps)&&ps!=pe);ans*=f;return true;

#endif

}const int MAXOUT=;   //*(int(*)[10])p

char bufout[MAXOUT], outtmp[],*pout = bufout, *pend = bufout+MAXOUT;

inline void write(){fwrite(bufout,sizeof(char),pout-bufout,stdout);pout = bufout;}

inline void out_char(char c){*(pout++)=c;if(pout==pend)write();}

inline void out_str(char *s){while(*s){*(pout++)=*(s++);if(pout==pend)write();}}

template <class T>inline void out_int(T x) {if(!x){out_char('');return;}

if(x<)x=-x,out_char('-');int len=;while(x){outtmp[len++]=x%+;x/=;}outtmp[len]=;

for(int i=,j=len-;i<j;i++,j--) swap(outtmp[i],outtmp[j]);out_str(outtmp);}

template<typename T, typename... T2>

inline int in(T& value, T2&... value2) { in(value); return in(value2...); }

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

#define Vec Point

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 1e5 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,tmp,K;

int a[maxn];

int solve(){

    int low,high;

    low = high = ;

    int ans = ;

    For(i,,N){

        if(a[i]){

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

            if(high > K) high = K;

            if(low > K) return -;

        }else{

            if(high >= ){

                low = max(low,);

            }else{

                ans++;

                low = ,high = K;

            }

        }

    }

    return ans;

}

int main()

{

    in(N,K);

    For(i,,N) in(a[i]);

    Pri(solve());

    #ifdef VSCode

    write();

    system("pause");

    #endif

    return ;

}

相关文章