C. Mixing Water

https://codeforces.com/contest/1359/problem/C

这题目要是看了editorial之后觉得一点都不难，回来起来我的思路是有问题的，我把它当做扩展GCD来求解了。不要问我为什么这么想，当时脑子就是比较混乱。

editorial里面说的就非常清楚，hot/cold只有两种情况：

• K hot water, K cold water, 那么温度就是(h+c)/2
• K+1 hot water, K cold water, 那么温度就是(k+1)h + kc / (2k+1)

但是无论如何最终温度都是>=(h+c)/2的. 如果(h+c)/2>=t的话，那么k=1就是最好的结果，只有t>(h+c)/2的时候才需要不断地增加热水.

令((k+1)h+kc) / (2k+1) == t的话，那么k = (h-t)/(2t-h-c). k可能是一个分数，所以最好检查一些int(k)和int(k)+1这两个值那么值得到的结果更接近t.

def run(h, c, t):
    if (h + c - 2 * t) >= 0:
        return 2

    a = h - t
    b = 2 * t - h - c
    k = int(a / b)
    val1 = abs((k + 1) * h + k * c - (2 * k + 1) * t)
    val2 = abs((k + 2) * h + (k + 1) * c - (2 * k + 3) * t)
    # val1 / (2k+1) <= val2 / (2k+3), return 2k+1
    if val1 * (2 * k + 3) <= val2 * (2 * k + 1):
        ans = 2 * k + 1
    else:
        ans = 2 * k + 3
    return ans