版权声明:本文为博主原创文章未经博主允许不得转载。 /XH/article/details/
一天欧姆诺诺姆来到了朋友家里,他发现了许多糖果有蓝色和红色两种。他知道每颗红色糖果重Wr克每颗藍色糖果重Wb克。吃一颗蓝色糖果会给他带来Hb的欢乐值吃一颗红色糖果会给他带来Hr的欢乐值。
欧姆诺姆最多只能吃C克的糖果而且每一颗糖果不能只吃一半。现在他想通过吃蓝色和红色的糖果来获得最大的欢乐值
样例解释:每一种糖果吃两颗即可。
输出最大可能获得的欢樂值
题解:很容易想的一个贪心,优先选择性价比高的糖果但是如果先尽可能的选择性价比高的糖果,然后在一个个去掉加上第二种糖果更新ans的话是会超时的。这里就要用一下数学的证明了其实当一个糖果的性价比比另一个低的时候,他的选择数量是不会超过sqrt(C)的利用这一点,在sqrt范围内枚举就不会超时了
这就把 wb>根号c 的枚举优化到了 根号 级
那么在wb*wr的空间里,就可以放 wr个b糖果得到 wr*hb
所以 若r糖果吃 wb个,那么b糖果吃 wr个更优
所以 r糖果 吃的个数不超过 wb个可以枚举 r糖果
因为 没吃wb个r糖果,都可以转为 吃 wr个b糖果替代
算法者贵在积累,深入浅出