c++题解

这个题首先需要明确一个点：
贪心思维！！！！！！！！！！！！
要最小化疫苗包的数量，就需要让1个疫苗包尽可能多注射。
具体见代码注释

include <iostream>
include <vector>
include <algorithm>

using namespace std;

void solve() {
    int n, k, d, w;
    if (!(cin >> n >> k >> d >> w)) return;
    
    vector<long long> t(n);
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }
    
    int packages = 0;
    int i = 0;
    
    while (i < n) {
        packages++;
        // 当前包在第 i 个患者最晚等待时刻开启
        long long open_time = t[i] + w;
        long long expire_time = open_time + d;
        
        int count = 0;
        // 尝试用当前包服务尽可能多的患者
        while (i < n && count < k) {
            // 检查患者 i 是否可以被当前包服务
            // 1. 患者到达时间不能超过疫苗过期时间
            // 2. 患者最晚接种时间 (t[i] + w) 必须 >= 疫苗开启时间 (open_time)
            //    这意味着患者愿意等到疫苗开启。
            if (t[i] <= expire_time && t[i] + w >= open_time) {
                i++;
                count++;
            } else {
                // 当前患者无法被当前包服务，跳出内层循环，外层循环会开新包
                break;
            }
        }
    }
    
    cout << packages << endl;
}

int main() {
    // 优化IO操作
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}

给个赞吧