[题目]大意
有(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)
本文章为转载内容,我们尊重原作者对文章享有的著作权。如有内容错误或侵权问题,欢迎原作者联系我们进行内容更正或删除文章。
赞 收藏 评论 举报相关文章