Cow Dance Show

题目描述

经过数月的排练，奶牛们已经几乎准备好进行她们一年一度的舞蹈演出；今年她们将表演著名的牛类芭蕾舞剧《Cowpelia》。 演出唯一尚未确定的方面是舞台的大小。大小为 $K$ 的舞台可以同时容纳 $K$ 头奶牛跳舞。牛群中共有 $N$ 头奶牛（$1 \leq N \leq 10,000$），并按她们必须在舞蹈中出场的顺序方便地编号为 $1 \ldots N$。每头奶牛 $i$ 计划跳舞持续特定的时间 $d(i)$。 最初，奶牛 $1 \ldots K$ 出现在舞台上并开始跳舞。当这些奶牛中最先完成表演的那一头结束后，她离开舞台，奶牛 $K+1$ 立即开始跳舞，依此类推，因此舞台上始终有 $K$ 头奶牛在跳舞（直到演出末尾我们开始不够奶牛可用）。当最后一头奶牛完成她的舞蹈部分时，演出在时间 $T$ 结束。 显然，$K$ 的值越大，$T$ 的值就越小。由于演出不能持续太久，输入会给出一个上界 $T_{max}$，表示 $T$ 允许的最大值。在该约束下，请确定 $K$ 的最小可能值。

输入格式

第一行输入包含 $N$ 和 $T_{max}$，其中 $T_{max}$ 是一个不超过 100 万的整数。 接下来的 $N$ 行给出奶牛 $1 \ldots N$ 的舞蹈时长 $d(1) \ldots d(N)$。每个 $d(i)$ 是范围 $1 \ldots 100,000$ 内的整数。 保证当 $K=N$ 时，演出一定能按时结束。

输出格式

输出使得整场舞蹈演出用时不超过 $T_{max}$ 的最小 $K$ 值。

5 8
4
7
8
6
4

4

提示

题目来源：Delphine 和 Brian Dean

标签: USACO|2017|Silver

来源

USACO|2017|Silver