codeforces 893D Credit Card 贪心 思维

codeforces 893D Credit Card

• 题目大意：

• 有一张信用卡可以使用，每天白天都可以去给卡充钱。到了晚上，进入银行对卡的操作时间，操作有三种：
• 1.(a_i>0) 银行会给卡充入(a_i)元
• 2.(a_i<0) 银行从卡中扣除(a_i)元
• 3.(a_i=0) 银行对你的卡进行评估，违背了规则就无权再使用此卡
• 规则1：卡内的余额不得超过(d)元
• 规则2：当(a_i=0)时，卡内的余额不能是负数
• 现在问为了维持信用的平衡，最少去银行几次。（去一次，充一次钱）

思路：

• 假设不给卡充钱，光靠银行自身的操作得到的余额，设定为最小值(minval)。而在迫不得已为了维持平衡给卡充钱后我们有最大值(minval)。
• 没有必要担心余额为负数的时候，只要我们在评估的早上充入足够多的钱就不会是负数。那么只考虑会超过余额限制(d)的情况。
• 在自然状态下得到的最小值，如果在评估那天小于0，我们只要让它回到0即可。同时如果最大值也小于0，说明卡内余额定为负数，就必须需要恢复到(d)元。因为尽可能的充钱，就可以减少去银行的次数，此时就必须去一次银行。
• 在(a_i e0)时，继续维护(minval,maxval)。如果最小值都大于了(d)，那么说明这已经是不可能在回到(d)以下了，输出-1。(minval le d)同时(minval > d)，那么说明通过充钱调节，将最大值回到(d)。最后输出去银行的次数。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main() {
    int n,d,maxval,minval,cnt;
    scanf("%d %d",&n,&d);
    for(int i=1;i<=n;++i) {
        scanf("%d",&a[i]);
    }
    maxval=0,minval=0;
    cnt=0;
    for(int i=1;i<=n;++i) {
        if(!a[i]) {
            if(minval<0) minval=0;
            if(maxval<0) {
                maxval=d;
                cnt++;
            }
        } else {
            minval+=a[i];
            maxval+=a[i];
            if(minval>d) {
                puts("-1");
                return 0;
            }
            if(maxval>d) {
                maxval=d;
            }
        }
    }
    printf("%d
",cnt);
    return 0;
}