ZJNU 1898 Cow Dance Show 二分

Cow Dance Show

Time Limit: 3000MS Memory Limit: 3000K Total Submissions: 82 Accepted: 13 Description

After several months of rehearsal, the cows are just about ready to put on their annual dance performance; this year they are performing the famous bovine ballet “Cowpelia”.

The only aspect of the show that remains to be determined is the size of the stage. A stage of size K can support K cows dancing simultaneously. The N cows in the herd (1≤N≤10,000) are conveniently numbered 1…N in the order in which they must appear in the dance. Each cow ii plans to dance for a specific duration of time d(i)d(i). Initially, cows 1…K appear on stage and start dancing. When the first of these cows completes her part, she leaves the stage and cow K+1 immediately starts dancing, and so on, so there are always K cows dancing (until the end of the show, when we start to run out of cows). The show ends when the last cow completes her dancing part, at time T.

Clearly, the larger the value of K, the smaller the value of T. Since the show cannot last too long, you are given as input an upper bound Tmax specifying the largest possible value of T. Subject to this constraint, please determine the smallest possible value of K.

Input

The first line of input contains N and Tmax, where Tmax is an integer of value at most 1 million.

The next NN lines give the durations d(1)…d(N) of the dancing parts for cows 1…N. Each d(i) value is an integer in the range 1…100,000.

It is guaranteed that if K=N, the show will finish in time.

Output

PRint out the smallest possible value of K such that the dance performance will take no more than Tmax units of time.

Sample Input

5 8 4 7 8 6 4 Sample Output

4

题目链接

题意：有n头牛要跳舞，每头牛都要上台跳舞表演，每只牛要表演的时间为ai，结束之后会有牛继续上台表演，知道所有牛跳舞结束（按顺序），问你需要多少个舞台才能在T时间内让所有牛都跳舞完。

解题思路：简单题，直接二分暴力即可，二分需要的舞台数mid，然后将每次更新这mid个舞台的时间就好了，每次找一个最短时间的舞台把ai加进去。最后最大的那个舞台时间就是mid个舞台时需要的最短时间。然而愚蠢的我把multiset写成了set，wa了五次，2333。