「EGOI2021」购物热 题解

题目分析

海蒂需要购买 $n$ 件商品，商场提供两种优惠方式：

1. 买三免一：一次购买至少3件商品，最便宜的那件免费
2. 百分比折扣：一次购买少于3件商品，享受 $q\%$ 折扣

目标是找到购买所有商品的最小总费用。

关键观察

1. 优惠机制分析

• 买三免一：节省的是组内最便宜商品的价格

  • 策略：让免费的商品价格尽可能高
  • 实现：将高价商品放在同一组

• 百分比折扣：实际支付 $(100-q)\%$ 的价格

  • 适合：低价商品单独购买

2. 最优分组策略

将商品按价格从高到低排序后：

• 优先让价格最高的3个商品组成一组
• 这样免费的是组内第三贵的商品（节省较多）
• 剩余商品再考虑组成新的三人组或单独购买

算法设计

贪心算法步骤

1. 排序：将商品价格从高到低排序
2. 分组：
   • 每3个商品一组，使用"买三免一"优惠
   • 支付组内最贵的2个商品的价格
3. 处理剩余商品：
   • 剩余0件：直接返回结果
   • 剩余1件：比较单独购买折扣 vs 与前面组合
   • 剩余2件：比较两种购买方式的成本

数学公式

• 三人组成本：$p_1 + p_2$（$p_1 \geq p_2 \geq p_3$，免费 $p_3$）
• 单独购买成本：$p \times (100 - q) / 100$

代码实现

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<ll> prices(n);
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }
    
    // 从高到低排序
    sort(prices.rbegin(), prices.rend());
    
    ll total = 0;
    int i = 0;
    
    // 处理完整的三人组
    while (i + 2 < n) {
        // 买三免一：支付最贵的两件
        total += prices[i] + prices[i + 1];
        i += 3;
    }
    
    // 处理剩余商品
    if (i < n) {
        if (n - i == 1) {
            // 剩余1件：单独购买享受折扣
            total += prices[i] * (100 - q) / 100;
        } else if (n - i == 2) {
            // 剩余2件：考虑两种方案
            ll option1 = (prices[i] + prices[i + 1]) * (100 - q) / 100;  // 单独购买
            ll option2 = prices[i] + prices[i + 1] - min(prices[i], prices[i + 1]);  // 尝试找第三个商品组成三人组？
            // 实际上剩余2件只能单独购买享受折扣
            total += option1;
        }
    }
    
    cout << total << endl;
    return 0;
}

样例验证

样例1

输入: 7 10
      300 200 200 300 100 300 200
排序后: 300, 300, 300, 200, 200, 200, 100

分组:
- 组1: 300, 300, 300 → 支付 300+300 = 600
- 组2: 200, 200, 200 → 支付 200+200 = 400  
- 剩余: 100 → 支付 100×90% = 90
总费用: 600 + 400 + 90 = 1090 ✓

样例2

输入: 3 20
      1000, 500, 100
排序后: 1000, 500, 100

方案比较:
- 买三免一: 1000+500 = 1500 (免费100)
- 单独购买: (1000+500+100)×80% = 1600×0.8 = 1280
选择更便宜的1280 ✓

样例3

输入: 4 0
      200, 100, 300, 200
排序后: 300, 200, 200, 100

分组:
- 组1: 300, 200, 200 → 支付 300+200 = 500
- 剩余: 100 → 支付 100×100% = 100
总费用: 500 + 100 = 600 ✓

优化考虑

边界情况处理

• 当 $q = 0$ 时，单独购买无折扣
• 当 $q = 100$ 时，单独购买免费（但题目中 $p_i \geq 100$，不会出现）
• 商品数量很少时的特殊处理

更精细的策略

对于剩余商品，可以考虑：

• 拆散已有的三人组来优化
• 但这样会增加复杂度，对于本题数据范围简单的贪心已足够

复杂度分析

• 排序：$O(n \log n)$
• 分组计算：$O(n)$
• 总复杂度：$O(n \log n)$，适合 $n \leq 100000$

总结

本题的关键在于：

1. 发现价格排序的重要性
2. 理解两种优惠机制的经济原理
3. 设计贪心分组策略
4. 正确处理剩余商品的购买方式

通过简单的排序和贪心策略，就能高效解决这个购物优化问题。