#807. [USACO17JAN]Cow Dance Show SDance Show S
[USACO17JAN]Cow Dance Show SDance Show S
题目描述
经过几个月的排练,奶牛们基本准备好展出她们的年度舞蹈表演。今年她们要表演的是著名的奶牛芭蕾——“cowpelia”。
表演唯一有待决定的是舞台的尺寸。一个大小为K的舞台可以支持K头牛同时在舞台上跳舞。在牛群中的N头牛(1<=N<=10,000)按照她们必须出现在舞蹈中的顺序方便地编号为1..N。第i头牛计划跳d[i]的特定持续时间。一开始,第1..K头牛出现在舞台上并开始跳舞。当这些牛中的某一头牛首先完成了她的部分,她会马上离开舞台并且第K+1头牛会出现在舞台上并开始跳舞。所以,舞台上总有K头奶牛在跳舞(直到表演的尾声,奶牛不够的时候)。当最后一头奶牛完成了她的舞蹈部分,表演结束,共花了T个单位时间。
显然,K的值越大,T就越小。由于表演不能拖太长,你得知了指定T的最大可能值的上限T-max。请根据这个约束,确定K的最小值。
输入格式
第一行包括N和T-max两个整数(T-max<=1,000,000)。
接下来的N行给出了第1..n头牛跳舞的持续时间d[1]..d[n]。第i行包括一个整数d[i],1<=d[i]<=100,000.
保证K=N时表演会按时完成。
输出格式
输出在表演时间不大于T-max时的K的最小可能值。
样例
输入样例
5 8
4
7
8
6
4
输出样例
4