HBC24724msc的宠物,二分,树,数据结构,分治[USACO 2010 Feb S]Chocolate Eating题解

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

Bessie has received N (1

Bessie has received N (1 <= N <= 50,000) chocolates from the bulls, but doesn't want to eat them too quickly, so she wants to plan out her chocolate eating schedule for the next D (1 <= D <= 50,000) days in order to maximize her minimum happiness level over the set of those days. Bessie's happiness level is an integer that starts at 0 and halves (rounding down if necessary) over night as she sleeps. However, when she eats chocolate i, her happiness level increases by integer H_i H i ​ (1 <= H_i H i ​ <= 1,000,000). If she eats chocolates on a day, her happiness for that day is considered the happiness level after she eats the chocolates. Bessie insists that she eat the chocolates in the order that she received them. If more than one optimal solution exists, print any one of them. Consider a sequence of 5 chocolates to be eaten over a period of 5 days; they respectively bring happiness (10, 40, 13, 22, 7). If Bessie eats the first chocolate (10 happiness) on the first day and then waits to eat the others, her happiness level is 10 after the first day. Here is the complete schedule which turns out to maximize her minimum happiness: Day Wakeup happiness Happiness from eating Bedtime happiness 1 0 10+40 50 2 25 --- 25 3 12 13 25 4 12 22 34 5 17 7 24 The minimum bedtime happiness is 24, which turns out to be the best Bessie can do.

全网最全C++题库，助您挑战自我，突破极限，成为编程领域的佼佼者！

标签： HBC24724msc的宠物 二分 树 数据结构 分治[USACO 2010 Feb S]Chocolate Eating题解