题解 | #清楚姐姐买竹鼠#

贪心算法与分类讨论

针对此问题，最核心的策略是贪心算法（Greedy Strategy）。通过分析两种方案的效用，我们可以将最优解锁定在极少数的候选状态中。

1. 效用分析

• 方案 A 的单价为 。
• 方案 B 的平均单价为 。 对比两者，若 ，说明一次买 3 个方案 A 的成本低于或等于 1 个方案 B。此时方案 B 完全失效，最优解必然是全部选择方案 A。

2. 最优解构造

当方案 B 的平均单价更优（即 ）时，我们应尽可能多地使用方案 B。但由于方案 B 是“捆绑销售”（每份 3 只），在处理余数（）时会产生三种分支：

• 分支一（全散装）： 全部按方案 A 购买。成本为 。（仅当 极小时最优）
• 分支二（组合购买）： 尽可能多地买方案 B，剩下的部分用方案 A 补齐。
  • 方案 B 数量：
  • 方案 A 数量：
  • 成本：
• 分支三（溢出购买）： 为了享受方案 B 的低廉单价，多买一份方案 B 使得总数超过 。
  • 方案 B 数量：
  • 成本：

复杂度分析

• 时间复杂度： 只需进行常数次算术运算（除法、取模、乘法以及最小值比较），与输入规模 无关。
• 空间复杂度： 仅需存储几个 64 位整型变量。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b, x;
    cin >> a >> b >> x;

    ll ans = a * x;;
    if (3 * a > b) {
        ll q = x / 3;
        ll r = x % 3;
        ll t1 = q * b + r * a;
        ans = min(ans, t1);

        ll t2 = (q + 1) * b;
        ans = min(ans, t2);
    }

    cout << ans << endl;
}