题解：P11176 [ROIR 2018 Day1] 提高成绩

· · 题解

首先感谢这篇帖子里大佬的指点。

感谢这位大佬提供的单调性证明。

题目描述

以知三个整数 a,b,c 现在有不等式：

\frac{2a+3b+4c+5x}{a+b+c+x} \ge 4

求 x 最小（分式四舍五入）。

思路分析

因为是四舍五入，所以可以把不等式化为：

\frac{2a+3b+4c+5x}{a+b+c+x} \ge 3.5

这里就不需要四舍五入了。

我们会发现，随着 x 的增长算下来的答案也在增长。这符合了单调性，那这题不就是二分答案了吗。

证明单调性： 令 f(x)=\frac{2a+3b+4c+5x}{a+b+c+x} ，

则对于 任意 x_1<x_2：

f(x_1)-f(x_2) \\=\frac{(2a+3b+4c+5x_1)(a+b+c+x_2)-(2a+3b+4c+5x_2)(a+b+c+x_1)}{(a+b+c+x_1)(a+b+c+x_2)} \\ =\frac{(2a+3b+4c)(x_2-x_1)+5(a+b+c)(x_1-x_2)}{(a+b+c+x_1)(a+b+c+x_2)}<0

则 f(x) 在定义域上单调递增。

不会二分答案可以搜索自学。

代码比较简单，就不放了。