#PU690. USACO 2017 January Contest, Silver — Problem 1. Cow Dance Show

    ID: 1461 传统题 文件IO:cowdance 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:jan17来源:usaco.orgscoring:equal_test_cases二分答案

USACO 2017 January Contest, Silver — Problem 1. Cow Dance Show

USACO 2017 January Contest, Silver — Problem 1. Cow Dance Show

题目描述

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 KK can support KK cows dancing simultaneously. The NN cows in the herd (1≤N≤10,0001 \leq N \leq 10,000) are conveniently numbered 1…N1 \ldots 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…K1 \ldots K appear on stage and start dancing. When the first of these cows completes her part, she leaves the stage and cow K+1K+1 immediately starts dancing, and so on, so there are always KK 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 TT. Clearly, the larger the value of KK, the smaller the value of TT. Since the show cannot last too long, you are given as input an upper bound TmaxT_{max} specifying the largest possible value of TT. Subject to this constraint, please determine the smallest possible value of KK.

输入格式

The first line of input contains NN and TmaxT_{max}, where TmaxT_{max} is an integer of value at most 1 million. The next NN lines give the durations d(1)…d(N)d(1) \ldots d(N) of the dancing parts for cows 1…N1 \ldots N. Each d(i)d(i) value is an integer in the range 1…100,0001 \ldots 100,000. It is guaranteed that if K=NK=N, the show will finish in time.

输出格式

Print out the smallest possible value of KK such that the dance performance will take no more than TmaxT_{max} units of time.

数据范围

(见题面原文)

样例

样例 1

5 8
4
7
8
6
4
4
Problem credits: Delphine and Brian Dean