不再赘述题目了。

这是一道典型的分数规划题目。可以参考一下 这里 的内容。这里主要讲一下笔者自己在做题时遇到的一些困惑。

为什么可以二分

我们以$x[i]=1$表示取第$i$种材料，$x[i]=0$表示不取。那么最后的答案会有$ans=\sum\frac{v[i]x[i]}{c[i]x[i]}$

我们将该式子变形一下，变成$\sum c[i]x[i]ans-\sum v[i]x[i]=0$，因此，可以设$F(ans)=\sum c[i]x[i]ans-\sum v[i]x[i]$

因为$\sum c[i]x[i]$显然为正数，所以$F(ans)$单调，所以可以通过二分找零点。

为什么可以贪心

现在确定了二分的可行性，需要考虑如何二分，也即考虑check函数。

假设我们现在二分出了一个答案$ans_{mid}$，我们要考虑这个答案的可行性，也即比较$ans_{mid}$和$\sum\frac{v[i]x[i]}{c[i]x[i]}$，注意到我们要求最大值，如果我们能找到一组合法的$x[i]$使得$\sum\frac{v[i]x[i]}{c[i]x[i]}>ans_{mid}$，也即存在一种取法比当前答案更大，这代表我们答案可以更大。

但是我们发现$\sum\frac{v[i]x[i]}{c[i]x[i]}>ans_{mid}$不好判断，因此将该式子变形成$\sum x[i](c[i]ans-v[i])<0$这个式子和前面的式子是等价的，但是这个式子和零比较，更好判断。现在我们只要找到一种取法能使得变形后的式子小于零，那么就能使原式成立，也即答案可以更大。那么显然，想找是否存在一组取法让式子小于零，那就取$c[i]ans-v[i]$最小的就好。因此贪心也成立。