Educational Codeforces Round 88 (Rated for Div. 2) C. Mixing Water（数学/二分） 题意 题解 代码
题目链接：https://codeforces.com/contest/1359/problem/C
热水温度为 $h$，冷水温度为 $c (c < h)$，依次轮流取等杯的热冷水，问二者在一容器中混合至最接近温度 $t$ 最少需要取多少杯。
题解
设取了 $x$ 杯热水，那么总的温度有两种情况：
- 取的冷水杯数与热水相同：$frac{xh + xc}{2x}$
- 取的冷水杯数比热水少一杯：$frac{xh + (x - 1)c}{2x - 1}$
第一种情况：
$frac{xh + xc}{2x} = frac{h + c}{2}$，所以只要取的热冷水杯数相同，总温度恒为 $frac{h + c}{2}$ 。
第二种情况：
$frac{xh + (x - 1)c}{2x - 1} = frac{x(h+c)-c}{2x-1}$，求导得：$frac{c-h}{(2x-1)^2}$，即当 $x≥1$ 时原函数单调递减，$frac{x(h+c)-c}{2x-1} = frac{h+c}{2 - frac{1}{x}} - frac{c}{2x-1}$，将 $x = 1$ 和 $x = + infty$ 代入得值域为：$[frac{h + c}{2}, h]$ 。
综上：
- 如果 $t≥h$，因为值域为 $[frac{h + c}{2}, h]$，此时与 $t$ 相差最小的就是 $h$，所以输出 $1$ 即可。
- 同理，如果 $t≤frac{h + c}{2}$，输出 $2$ 即可。
- 否则二分查找总温度小于等于 $t$ 的最小杯数 $ans$，与大于 $t$ 的最小杯数 $ans-1$ 取与 $t$ 之差的较小者即可。
代码
#include <bits/stdc++.h> using namespace std; int h, c, t; double cal(double x) { return (x * h + (x - 1) * c) / (2 * x - 1); } void solve() { cin >> h >> c >> t; if (t >= h) cout << 1 << " "; else if (2 * t <= h + c) cout << 2 << " "; else { int ans = 0; int l = 1, r = 1e6; while (l <= r) { int mid = (l + r) / 2; if (cal(mid) <= t) { ans = mid; r = mid - 1; } else l = mid + 1; } double mi = min(abs(t - cal(ans - 1)), abs(t - cal(ans))); if (ans - 1 >= 1 and mi == abs(t - cal(ans - 1))) cout << 2 * ans - 3 << " "; else cout << 2 * ans - 1 << " "; } } int main() { int T; cin >> T; while (T--) solve(); }