CF1804B题解

szh_AK_all · 2023-08-03 10:16:00 · 题解

题目传送门

题意加分析

一共有 n 个病人来看病，每个病人都需要 1 剂量。但每个包装的剂量是有限的，所以要用到多个包装。要求出最少需要多少包装（每个包装的剂量为 k）。

既然是“最少”，那么我们要让每个包装尽量用完。也就是，如果第 i 个包装还可以用，就不要用第 i+1 个包装。那什么情况下不可以用呢？一、当已用时间超出了药的寿命加上病人最大的等待时间时，这箱药便不能再用了；二、如果这箱药用完了，也只能用另一箱了。

我们用变量 zh 来记录药的箱数，用 f 来记录第一个使用第 zh 箱药的病人。如果这箱药还可以用，那么让下一个病人进来，否则，更新 zh，将 f 改为这位病人的号码（第 n 为病人的号码为 n）。最后输出 zh 即可。

Code

#include<iostream>
using namespace std;
int a[200005];
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int n,k,d,w;
        cin>>n>>k>>d>>w;
        int zh=1,f=1;
        for(int j=1;j<=n;j++)
        {
            cin>>a[j];
            if((j-f>=k)||((a[j]-a[f])>d+w))
            zh++,f=j;
        }
        cout<<zh<<endl;
    }
    return 0;
}