CF126A 题解

Vitamin_B · 2024-03-28 21:47:48 · 题解

前置芝士

浓度问题中的十字交叉法（小学奥数）。

介绍一下十字交叉法（如果已经学过请跳过）：若冷水温度 t1，热水温度 t2，需求的温度为 t0，则冷热水流速之比为 t2-t0:t0-t1（注意不是 t0-t1:t2-t0）。

证明：\frac{(t2-t0)\times t1+(t0-t1)\times t2}{(t2-t0)+(t0-t1)}=\frac{t2\times t1-t0\times t1+t0\times t2-t1\times t2}{t2-t1}=\frac{t0(t2-t1)}{t2-t1}=t0。

思路

既然知道了流速之比，那我们只需要枚举冷水流速 y1（枚举热水流速同理），热水流速就可以 O(1) 得出：y2=\lceil y1\times\frac{t0-t1}{t2-t0}\rceil，这里可以用 double，但是为了避免精度误差，这只蒟蒻还是使用了整数运算的方法：y2=\lfloor\frac{y1\times(t0-t1)+t2-t0}{t2-t0}\rfloor。当然如果此时 y1>x2 了就不用继续枚举了，直接退出循环。如果当前答案比之前的最优答案不劣（\frac{y2}{y1}\le\frac{ans1}{ans0}），那就更新答案。同样为了避免精度误差，我们可以把这个式子改变一下：\frac{y2}{y1}\le\frac{ans2}{ans1}\to\frac{y2}{y1}\times y1\times ans1\le\frac{ans2}{ans1}\times y1 \times ans1\to y2\times ans1\le ans2\times y1。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t1, t2, x1, x2, t0, ans1, ans2, t;
int main () {
    ios::sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    cin >> t1 >> t2 >> x1 >> x2 >> t0;
    if (t0 == t1)
        if (t0 == t2)
            cout << x1 << ' ' << x2;
        else
            cout << x1 << " 0";
    else if (t0 == t2)
        cout << "0 " << x2;
    else {
        ans2 = x2;
        for (int i = 1; i <= x1; ++ i) {
            t = ((ll) (t0 - t1) * i + t2 - t0 - 1) / (t2 - t0);
            if (t > x2)
                break ;
            if ((ll) t * ans1 <= (ll) ans2 * i)
                ans1 = i, ans2 = t;
        }
        cout << ans1 << ' ' << ans2;
    }
    return 0;
}