P4801 购物竞赛（基础）

解题思路

1. 读懂题目：有 N 种商品，每种商品的总价是 M 元，被平均拆成 K 个包装，所以每个包装里装的"价值"就是 M/K。购物车只能放 L 个包装，我们要让购物车里的价值最大，也就是尽量装"平均价值"高的包装。

2. 打个比方：就像在超市里挑小袋零食，哪个品牌的每一袋"最实惠"（平均价值最高），就优先往购物车里放；购物车放不下了，就停止。

3. 第一步：对每种商品算出它每个包装的平均价值 M/K，然后按平均价值从高到低排序。注意比较的时候用"交叉相乘"：比较 a.price/a.packages 和 b.price/b.packages，就是比较 a.price×b.packages 和 b.price×a.packages，这样不会出现小数误差。

4. 第二步：从平均价值最高的商品开始装。如果这种商品全部的 K 个包装都能装下，就把它的总价 M 全部累加到答案里（因为 K 个包装正好值 M 元）。

5. 第三步：如果这种商品的 K 个包装装不完了，就只装购物车剩下的几个位置，把"剩余位置数 × M/K"的价值加进答案，然后结束。

6. 边界情况：如果 L 非常大，把所有商品都装完购物车还有空位，答案就是所有 M 的总和；如果 L 非常小，就只装平均价值最高的那几个包装，剩下的位置空着也没关系。

参考代码

// P4801 购物竞赛：按每个包装的平均价值从高到低装进购物车，装满 L 个包装即可
#include <iostream>
#include <algorithm>
using namespace std;

struct Goods {
    long long price;    // 这种商品的总价 M
    long long packages; // 这种商品被拆成的包装数 K
};

Goods goods[100005];    // 每种商品

// 按每个包装的平均价值 M/K 从大到小排序（用交叉相乘避免浮点误差）
bool cmp(const Goods& a, const Goods& b) {
    return (long double)a.price * b.packages > (long double)b.price * a.packages;
}

int main() {
    int N, L;
    cin >> N >> L;
    for (int i = 0; i < N; i++) cin >> goods[i].price >> goods[i].packages;
    // 平均价值高的商品排在前面，优先装满它的包装
    sort(goods, goods + N, cmp);
    long double ans = 0;   // 购物车中装载的总价值
    long long filled = 0;  // 已经装入的包装数量
    for (int i = 0; i < N; i++) {
        if (filled + goods[i].packages <= L) {
            // 这种商品的包装能全部装下，贡献的价值正好是总价
            ans += goods[i].price;
            filled += goods[i].packages;
        } else {
            // 只装下剩下的 take 个包装
            long long take = L - filled;
            ans += (long double)take * goods[i].price / goods[i].packages;
            filled = L;
            break;
        }
    }
    // 题目保证答案是整数，四舍五入输出
    cout << (long long)(ans + 0.5L) << endl;
    return 0;
}

复杂度分析

主要时间是排序，N 种商品排序需要 O(N log N)；排序后再扫描一遍挑选包装，需要 O(N)。所以总时间复杂度是 O(N log N)，空间复杂度是 O(N)。