题目描述

给定 n 瓶酸奶的过期日期，过期即日起就不能再喝，同时每天最多喝 k 瓶，问最多可以喝几瓶

1≤N≤5000

样例

输入样例：

4
2 1
1 1
5 1
3 2 3 2 3
2 2
1 1
6 2
1 1 1 7 7 7

输出样例：
Case #1: 1
Case #2: 3
Case #3: 2
Case #4: 5

-> yxc视频里的代码在这里 <-

yxc视频里没有讲的另一种思路

思路

n瓶酸奶，最多n天就一定可以喝完
利用了可以提前喝，不能过期喝的这个性质，具体做法见代码

时间复杂度

$O(n)$

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010;
int n, k;
int s[N];  // s[i]表示有 s[i]瓶酸奶必须在i天之前喝，i天之后就过期不能喝

int main()
{
    int T;
    cin>>T;
    for(int cas = 1; cas <= T; cas ++)
    {
        cin>>n>>k;
        memset(s, 0, sizeof s);
        for(int i = 0; i < n; i++)
        {
            int x;
            cin>>x;
            s[ min(x, n) ] ++; //最多n天就一定可以喝完
        }

        for(int i = n; i >= 1; i--)
        {
            if(s[i] > k)  //当天喝不完 提前给前一天喝
            {
                s[i-1] += s[i] - k;
                s[i] = k;
            }
        } //s[0] 里面就是所有来不及喝的

        int res = n - s[0];
        printf("Case #%d: %d\n", cas, res);
    }
    return 0;
}