P15256 [USACO26JAN2] Purchasing Milk B 题解

题意

第 $i$ 种交易：

• 花费 $a_i$
• 获得 $2^{i-1}$ 桶
• 可无限购买

对于每个询问 $x$，求购买 至少 $x$ 桶牛奶 的最小花费。

注：文中的 $a_i$ 指的是题目条件所给的 $a_i$，而 $\text{a}[i]$ 指的是维护的单位容量价格单调不劣的数组 vector<ll> a。

思路

首先题目说到了花费 $a_i$ 可以购买 $2^{i-1}$ 桶牛奶，这就给了提示本题的思路应该是二进制下贪心。

看了一下大家的题解，好像多数都是对二进制下 $x$ 从低位往高位遍历的，不过我第一时间的想法是从高位往低位更新答案，如果该位置是 $1$，那么 $\text{a}[i]$ 是一定要选的；如果该位置是 $0$，那么 $\text{a}[i]$ 可以选，此时已经完成购买任务了，记录下最优答案，又或者是不选，继续向后遍历。

最终的答案自然是取所有购买方案的最小值。

::::info[价格预处理]

直接从 $i=0$ 开始存就可以直接让 $\text{a}[i]$ 表示花费 $\text{a}[i]$ 可以购买 $2^{i}$ 桶牛奶。

如果 $a_i > 2 \times \text{a}[i-1]$，说明两个小桶更便宜，应更新为 $\text{a}[i] = \min(a_i,2 \times \text{a}[i-1])$ 保证单位容量价格单调不劣。

::::

复杂度

由于 $1 \leq x \leq 10^9 < 2^{30}$，因此数组 a 最多只需要开到 $30$，从高位向低位更新答案，复杂度为 $O(Q \log_2 10^9) \approx O(30Q)$。

放在最后

::::success[代码]

#include <bits/stdc++.h>
#define ll long long
#define i128 __int128
#define il inline
#define befaster cin.tie(0)->sync_with_stdio(0)
using namespace std;

int n, q;
vector<ll> a;

int main()
{
    befaster;
    cin >> n >> q;
    a.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i > 0)
            a[i] = min(a[i], a[i - 1] * 2ll);
    }
    for (int i = n; i <= 30; i++)
        a.emplace_back(a.back() * 2ll);
    while (q--)
    {
        ll x;
        cin >> x;
        ll rest = x;
        ll res = 0, best = 1e14;
        for (int i = 30; i >= 0; i--)
        {
            ll pow2 = 1ll << i;
            if (rest >= pow2)
            {
                res += a[i];
                rest -= pow2;
            }
            else
                best = min(best, res + a[i]);
        }
        cout << min(res, best) << '\n';
    }
    return 0;
}

::::