自动搬运

查看原文

来自洛谷，原作者为

	BriMon 我曾经落败，如今依然

搬运于2025-08-24 21:50:40，当前版本为作者最后更新于2018-06-04 21:53:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实挺不好意思的，我也不是自己想出来的这道题，也是借鉴了题解；

但是我想把我对这道题的理解说出来，这样可以帮助到更多的不理解的人；

这道题其实一眼就知道二分答案， 想都没想直接敲，16分，what...f？

回过头再仔细读题解， 发现这题并不简单；

我们知道a[1],a[2]...a[n],也知道k,我们要求a[1]/b[1]+a[2]/b[2]+...+a[n]/b[n]的最小值,其中Σbi=k;

这仿佛不是一个寻常的二分可以搞定的；

仔细琢磨题解你会发现，我们要让其中每一层楼，不加入一个牛，比加入一个牛更优，什么意思？

就是我们考虑， 如果这个楼层加一个牛比不加一个牛优，那我们肯定会把别的楼层的牛拿过来给他；

那我们该怎么表示这个抽象的东西呢？

我们设:ti = ai / (ci + 1) - ai / ci , ci是第i层楼的牛数量；

这样我们设出来的ti，就表示这个楼层多一只牛的改变量，我们要求的最终答案，肯定是每层楼的ti最接近，否则我们肯定可以找一只牛放里面；

化简一下得到 ti = ai / (ci * (ci + 1)) ,移项得 ci^2 - ci - ai/ti = 0；

发现我们只要枚举ti， 就可以通过简单的小学数学，把ci算出来；

然后开开心心的二分；

最后如果有空闲的牛就直接乘以r，然后减掉就行了，为什么要乘r？

因为我们二分出来了一个ti,这个ti保证是所有楼层的ti（因为他们最接近的时候才是答案），所以直接乘ti，当成他们的贡献！

有几个坑点，首先记得开long long，还得记得二分一个小数一定要设eps...

顺便推广一下blog，欢迎各位大佬拍砖。

Code：下面题解里有