YBTOJ:喂养宠物

[题目]大意

有(n)只兔兔，每只兔兔单独时都需要吃(hunger_i)的食物量，假如有同食者，那么每个同食者会让它需要多吃(greed_i)的食物量。假如小明最多能提供(totalFood)的食物，那么他最多能养多少只兔兔。

题目分析

养的兔子越多，所需食物量越大，可见答案具有单调性，用二分答案做。
答案的上下限：
下限很明显就是(0)，上限就是兔兔的总数即(n)，(n)的最大值是(50)，所以上限为(50)。
再确定二分条件：
“在养mid只兔兔时小明是否能够提供足够食物”。
怎么判断呢？
每个兔兔的代价是不同的，但是它们的贡献是相同的，所以可以用贪心做，先预处理出所有兔兔的代价，当选(mid)只兔兔时，第(i)只兔兔的代价为(hunger_i+greed_i*(mid-1))
然后(sort)大法~~
然后用(sum)累加前(mid)个，最后判断(tot geq sum)

(Code)

本文章为转载内容，我们尊重原作者对文章享有的著作权。如有内容错误或侵权问题，欢迎原作者联系我们进行内容更正或删除文章。

相关文章