ABC 446 C题解

· · 题解

题目大意

餐厅营业 n 天，每天需要完成下面三个操作：

  1. 早晨：购买 a_i 个鸡蛋。
  2. 中午：使用 b_i 个鸡蛋。（按照购买的顺序使用的，因此也就是遵循着 FIFO 的原则）
  3. 晚上：丢弃所有库存超过 d 天的鸡蛋。

开始时没有鸡蛋，且保证中午使用时不会出现鸡蛋不够的情况。求第 n 天晚上丢弃后剩余的鸡蛋数量。

解题思路

这道题最重要的部分就是模拟鸡蛋的先进先出和过期丢弃规则。

由于关注到先进先出（FIFO），我们自然会想到用队列来解决。

我们可以使用两个队列来分别存储鸡蛋的购买天数和对应批次的鸡蛋数量。

具体的模拟过程其实就是按照题目所说的去做，没有什么难点。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],b[N];
queue<int> q1,q2;
int q,n,m;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>q;
    while(q--)
    {
        while(q1.size()) q1.pop();
        while(q2.size()) q2.pop();
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        for(int i=1;i<=n;i++)
        {
            if(a[i]) q1.push(i),q2.push(a[i]);
            int t=b[i];
            while(t&&q2.size())
            {
                if(q2.front()>t) q2.front()-=t,t=0;
                else t-=q2.front(),q2.pop(),q1.pop();
            }
            while(q1.size()&&i-q1.front()>=m) q2.pop(),q1.pop();
        }
        int ans=0;
        while(q2.size()) ans+=q2.front(),q2.pop();
        cout<<ans<<"\n";
    }
    return 0;
}

提交记录