翻译

有两种不限量的水：

温度为 h 的热水
温度为 c 的冷水(c < h)

你需要交替执行以下程序：

打一杯热水倒入无限容量的桶内
打一杯冷水倒入无限容量的桶内
打一杯冷水。。。
等等

第一杯必须是热水

桶开始是空的，你至少要倒进去一杯水。桶内水的温度是所有倒入水的温度的平均值。

你想要桶内的温度无限接近 t。比方说，桶内的水的温度是 tb，那么他希望 |tb - t| 的值最小。

需要多少杯水使桶内水的温度最接近 t？如果有多个答案，输出最小的那个。

输入格式

输入整数 t 表示测试用例组数。

每一组测试用例输入一行三个数字，h c t，用空格分隔。

输出格式

每一个测试用例输出最小的杯数。

分析

这道题暴力是不行的，所以考虑用二分法，以及可以用公式来简化二分法的代码。首先预处理以下情况

如果，温度等于最高温度则，只要一杯水
如果，温度小于等于 (h + c) / 2，那么只需要两杯水
如果，温度大于三杯水的平均温度 (h * 2 + c) / 3，分为两种情况，接近最高温度则是 1 杯水，接近平均温度则是 3 杯水
其余情况就需要特别计算了

首先注意以上几种情况计算时，都是用乘法代替除法，是因为如果不能整除，比较会有精度问题，导致结果错误，用乘法可以保证结果为整数，以下思路也许要这样处理。

我推导出了神奇的公式，大概需要 x 杯水，x = (t - c) / (2 * t - h - c)，为了结果准确，我计算了 x前后十几个值，取出最小的结果。其实大概三个就可以。

关键就是要用惩罚代替除法，因为手懒错了十几次。

代码(PyPy3)

# https://codeforces.com/problemset/problem/1359/C
 
import sys
import os
import heapq
import math
 
try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass
 
T = int(input())
 
def printd(value):
    # print(value)
    pass
 
for _ in range(T):
    arr = list(map(int, input().split(" ")))
    h, c, t = arr[0], arr[1], arr[2]
    
    result = 1
    if t == h:
        result = 1
    elif t * 2 <= (h + c):
        result = 2
    elif t * 3 >= (h * 2 + c):
        result = 1 if abs(h * 3 - t * 3) <= abs((h * 2 + c) - t * 3) else 3
    else:
        x = (t - c) / (2 * t - h - c)
        x = int(x)
 
        start = max(2, x - 5)
        top = 99999999999
        bottom = 1
        for i in range(start, start + 15):
            bottomi = abs(i * 2 - 1)
            topi = abs((h * i + c * (i - 1)) - bottomi * t)
            if top * bottomi > topi * bottom:
                top = topi
                bottom = bottomi
                result = i * 2 - 1
                
    print(result)

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.06.02 长春