HBC24054面积,计算几何[USACO 2017 Jan S]Cow Dance Show题解 （每日一词：cows）

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

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 sizeKcan supportKcows dancing simultaneously. TheNcows in the herd are conveniently numbered 1…Nin the order in which they must appear in the dance. Each cowiplans to dance for a specific duration of timed. Initially, cows 1…Kappear on stage and start dancing. When the first of these cows completes her part, she leaves the stage and cowK+1immediately starts dancing, and so on, so there are alwaysKcows dancing . The show ends when the last cow completes her dancing part, at timeT. Clearly, the larger the value ofK, the smaller the value ofT. Since the show cannot last too long, you are given as input an upper bound TmaxT_{max}Tmaxspecifying the largest possible value ofT. Subject to this constraint, please determine the smallest possible value ofK.

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,0001 leq N leq 10,0001≤N≤10,000) are conveniently numbered 1…N1 ldots N1…N in the order in which they must appear in the dance. Each cow i plans to dance for a specific duration of time d(i). Initially, cows 1…K1 ldots K1…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 TmaxT_{max}Tmax​ specifying the largest possible value of T. Subject to this constraint, please determine the smallest possible value of K.

不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC24054面积 计算几何[USACO 2017 Jan S]Cow Dance Show题解