两种物品凑数求最小花费

模板题

有两种物品。第一种权重 \(A\)，花费 \(B\)。第二种权重 \(C\)，花费 \(D\)。每种物品均可以买任意个，求权重总和至少为 \(n\) 的情况下，最小的花费 \(ans\)。

结论：设第一种为性价比高的物品。第二种物品购买的数量一定在 \(0 \sim A\) 之间。其中 \(A\) 是性价比高的物品的权重。于是枚举第二种物品的数量即可。时间复杂度 \(O(A)\)。

ll Trick1(ll a, ll b, ll c, ll d, ll n)
{
    ld A = 1.0 * a / (1.0 * b), B = 1.0 * c / (1.0 * d);
    if (A < B)
    {
        swap(a, c);
        swap(b, d);
    }
    ll ans = INF;
    fr(i, 0, a)
    {
        ll sum = 0;
        ll cha = n - i * c;
        sum = i * d;
        if (cha >= 0)
            sum += ((cha + a - 1) / a) * b;
        ans = min(ans, sum);
    }
    return ans;
}