📝 题目大意

有四种规格的瓶装冰茶：0.25L（Q 日元）、0.5L（H 日元）、1L（S 日元）、2L（D 日元），每种无限供应。求恰好购买 N 升所需的最小金额。

💡 解题思路

1. 题目分析：乍看是背包/DP，但四种规格之间存在倍数关系（0.25 → 0.5 → 1 → 2，每次翻倍），且 $N$ 高达 $10^9$，价格 $Q,H,S,D$ 高达 $10^8$，答案可超 32 位整数。这提示我们应当用贪心而非 DP。

2. 算法推导：

   • 首先进行价格归一化：用小瓶凑出大瓶的容量，如果更便宜就更新大瓶的"等效价格"。
     • H = min(2*Q, H)：用两瓶 0.25L 凑出 0.5L 的成本是 $2Q$，取 $\min(2Q, H)$ 作为 0.5L 的最优单价。
     • S = min(2*H, S)：同理，两瓶 0.5L（已归一化）凑 1L，取 $\min(2H, S)$。
     • D = min(2*S, D)：两瓶 1L 凑 2L，取 $\min(2S, D)$。
   • 归一化后满足：大瓶的单位容量价格不会高于小瓶（即 $D/2 \le S$，$S/2 \le H$，$H/2 \le Q$）。因此贪心策略成立：优先使用最大规格。
   • 最终方案：用 $\lfloor N/2 \rfloor$ 瓶 2L 装（D），余数 $N \bmod 2$ 用 1L 装（S）补齐。即 ans = (N/2)*D + (N%2)*S。

3. 边界与细节：

   • 整数溢出：N 和价格均为 $10^8 \sim 10^9$ 级别，(N/2)*D 可达 $5 \times 10^{16}$，必须用 long long（64 位整数）。代码中通过 (long long)(N/2)*D 强制转换。
   • N 为奇数：余数 1L 只能用 S（归一化后 $S \le 2H \le 4Q$，是最优的 1L 方案）。
   • N=1 且 D 极便宜：比如样例 2，$D=10$ 但 $N=1$，不能买 2L 装，只能买 1L 装花费 $S=100$。代码正确处理。

⏱️ 复杂度分析

• 时间复杂度：仅若干次 $\min$ 操作和一次乘加，与 $N$ 无关，$O(1)$。
• 空间复杂度：仅使用常数个变量，$O(1)$。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;

int Q, H, S, D, N;
long long ans;  // 答案可能很大，需用 64 位整数

int main() {
    scanf("%d%d%d%d%d", &Q, &H, &S, &D, &N);

    // 价格归一化：用小瓶的等效价格更新大瓶，确保大瓶单位价格不高于小瓶
    H = min(2 * Q, H);   // 0.5L 的最优成本 = min(两瓶0.25L, 一瓶0.5L)
    S = min(2 * H, S);   // 1L   的最优成本 = min(两瓶0.5L,  一瓶1L)
    D = min(2 * S, D);   // 2L   的最优成本 = min(两瓶1L,    一瓶2L)

    // 贪心：尽可能用 2L 装，余数用 1L 装补齐
    ans = (long long)(N / 2) * D + (N % 2) * S;

    printf("%lld\n", ans);
    return 0;
}