题解 P6013【压岁钱】

Hexarhy · 2020-01-28 16:25:41 · 题解

被评测机卡到交 5 次才过……

自闭。

解题思路

作为比赛的签到题，一看就是模拟。

直接根据每天的操作模拟即可。步骤如下：

• 在每一天伊始，都要更新自己的压岁钱，因为有的可能解封了。

• 当 t=1，直接加余额。

• 当 t=2，判断余额是否足够（包括等号）。不够（即小于）则统计答案，否则直接扣余额。

• 当t=3，记录封印和解封时间，同时扣除余额。为了方便每天更新压岁钱，我们用set按照时间顺序记录封印。

• 在每一天伊始，更新自己的压岁钱时，直接用set的第一个元素判断是否为当前时间即可。

若忽略set的复杂度，则时间复杂度 O(m)。但其实实际得分依然为 100\%。

实现细节

1. 封印之后，余额要减。

3. 判断余额是否足够时，注意等号。

4. set解封时判断是否是当前日期，使用while而非if，因为可能一天同时解封多个。

参考代码

使用类封装。当然可以写成一般函数的形式。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
ll m,t,a,b;
class money//别介意
{
private:
    ll total,ans;
    struct Lock
    {
        ll v,date;//封印金额和解封时间
        bool operator<(const Lock& x)const
        {
            return date<=x.date;//按时间排序
        }
    };
    set <Lock> locked;
public:
    void update(const ll& now)//每天第一步：更新压岁钱（解封）
    {
        while(!locked.empty() && locked.begin()->date==now)//实现细节4
        {
            total+=locked.begin()->v;
            locked.erase(locked.begin());//别忘了删除记录
        }
    }
    void save(const ll& v)//存钱
    {
        total+=v;
    }
    void cost(const ll& v)//花费
    {
        if(total<v)
         ans++;//钱不够了统计答案
        else
         total-=v;
    }
    void lock(const ll& v,const ll& date)//封印
    {
        locked.insert(Lock{v,date});
        total-=v;//别忘了减
    }
    ll unhappy(void)
    {
        return ans;
    }
}q;
int main(int argc, char const *argv[])
{
    //输入最好用scanf()快些。本题输入量不小。
    cin>>m;
    for(ll i=1;i<=m;i++)
    {
        q.update(i);
        cin>>t>>a;
        switch(t)
        {
            case 1:q.save(a);continue;
            case 2:q.cost(a);continue;
            case 3:cin>>b;q.lock(a,b);continue;
        }
    }
    cout<<q.unhappy()<<endl;
    return 0;
}