cf913c.md

提示 1： 一般促销是买得越多单价越便宜，怎么根据这个逻辑调整？

提示 2： 容量总为 $2^k$ 的形式，这能说明什么？

提示 3： 如果已经调整为更大量的商品更便宜，接下来应该怎么购买？

我们先依据提示 1 进行调整。由于 $2^k=2^{k-1}+2^{k-1}$ ，我们可以发现一份更大的柠檬水可以拆为两份小柠檬水。

于是大份柠檬水的价格应该不超过小份柠檬水的两倍，否则应该用两份小的柠檬水凑。

按照上述逻辑，我们假设 $2^0,2^1,...,2^k$ 都已经达到了最小成本，其中最小的单价一定由 $2^k$ 容量的达到。

于是， $2^{k+1}$ 可以选择自己原先的单价，也可以选择 $2^k$ 的单价（上述拆分柠檬水的过程），两者取最小值，也同时使得 $2^{k+1}$ 单价最低。

因此这样调整后，最大的包装单价最低。

整体上很像一个无套利条件。

接下来，我们要使得购买的柠檬水总量不小于 $L$ ，于是我们应该从单价更小的位置开始考虑，即从后向前遍历。

这里使用了贪心。为何这题贪心成立呢？在购买的总柠檬水一定时，选择更大量的柠檬水一定更好。

因为首先其单价更低，而如果不使用更大量的柠檬水，将需要一批更小量的柠檬水凑成同样的数量（因为从小到大的容量满足倍数关系），这样单价是更高的。

于是，我们从后往前贪心地买尽可能多的柠檬水，使得总量不超过 $L$ .

而这样，在遍历每个位置时会剩下一些柠檬水。除了剩下的柠檬水外，前面的贪心逻辑使得前半部分的单价是最低的。

而每次剩下的柠檬水有两种凑法：用更小的容量凑 / 直接用当前的容量凑（会使得购买总量可能大于 $L$ ）。枚举这两种情况即可。

为什么这样做有道理呢？我们假设我们最后购买了 $L'$ 升的柠檬水，那么考虑 $L,L'$ 二进制表示中从高到低第一个不同的位，则 $L'$ 在这一位后面应当全部等于 $0$ 。

而在上述过程中，我们 “用当前容量凑” 的过程，相当于枚举了所有可行的 $L'$ 并给予了其贪心的结果，使得最后得出总体最小值。

如果上述过程不太理解，可见代码。时间复杂度为 $\mathcal{O}(n)$ .

具体代码如下（只包含中间处理部分）——

def main():
    n, l = MII()
    nums = LII()
    for i in range(1, n):
        nums[i] = min(nums[i], nums[i-1] * 2)
    
    ans = inf
    cur = 0
    for i in range(n - 1, -1, -1):
        ans = min(ans, cur + nums[i] * ((l - 1) // (1 << i) + 1))
        v = l // (1 << i)
        l -= v << i
        cur += v * nums[i]
    
    print(ans)