礼盒排序 题解

题目分析

本题要求我们根据复杂的排序规则对若干礼盒进行排序。每个礼盒中有 $k$ 件商品，我们需要依据以下优先级（由高到低）进行排序：

1. 礼盒总价格（从小到大）
2. 礼盒中最贵的商品价格（从小到大）
3. 礼盒中最便宜的商品价格（从小到大）
4. 礼盒编号（从小到大）

输入保证 $n \le 1000$，$k \le 10$，数据规模很小，但规则稍多，适合用自定义排序的方式解决。

解题思路

对于每一个礼盒，我们需要事先计算出总价格、最大价格、最小价格这三个属性。然后按照排序规则编写一个比较函数，利用编程语言提供的排序函数（如 C++ 的 sort）对礼盒进行排序。最后按顺序输出礼盒的编号即可。

整体流程如下：

1. 读入 $n$ 和 $k$。
2. 循环读入每个礼盒的 $k$ 个商品价格，同时计算：
   • sum：价格总和
   • mx：价格的最大值
   • mn：价格的最小值
   • id：礼盒编号（从一开始）
3. 存储每个礼盒的这些信息（常用结构体完成）。
4. 调用 sort，传入自定义的比较函数 cmp：
   • 先比较 sum，小的在前；
   • sum 相同则比较 mx，小的在前；
   • mx 相同则比较 mn，小的在前；
   • 前面都相同则比较 id，小的在前。
5. 输出排序后的礼盒编号，用空格分隔。

由于数据范围很小，上述操作可以在时间限制内轻松完成。

参考代码

以下是 C++ 参考代码，并对关键部分做了注释。

cpp
复制
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// 定义礼盒的结构体，存储排序所需的所有信息
7struct Combo {
8    int sum;   // 总价格
9    int mx;    // 最大价格
10    int mn;    // 最小价格
11    int id;    // 礼盒编号（从1开始）
12};
13
14// 自定义排序比较函数
15bool cmp(const Combo &a, const Combo &b) {
16    if (a.sum != b.sum) return a.sum < b.sum; // 1. 总价格小的优先
17    if (a.mx != b.mx) return a.mx < b.mx;     // 2. 最大价格小的优先
18    if (a.mn != b.mn) return a.mn < b.mn;     // 3. 最小价格小的优先
19    return a.id < b.id;                       // 4. 编号小的优先
20}
21
22int main() {
23    int n, k;
24    cin >> n >> k;
25    vector<Combo> v(n); // 存储所有礼盒信息的动态数组
26
27    for (int i = 0; i < n; i++) {
28        v[i].sum = 0;            // 总价初始化为0
29        v[i].mx = -1;            // 最大值初始化为极小值
30        v[i].mn = 1e9;           // 最小值初始化为极大值
31        v[i].id = i + 1;         // 编号从1开始
32
33        for (int j = 0; j < k; j++) {
34            int x;
35            cin >> x;
36            v[i].sum += x;                      // 累加总价
37            v[i].mx = max(v[i].mx, x);          // 更新最大值
38            v[i].mn = min(v[i].mn, x);          // 更新最小值
39        }
40    }
41
42    // 使用自定义比较函数排序
43    sort(v.begin(), v.end(), cmp);
44
45    // 输出排序后的编号
46    for (int i = 0; i < n; i++) {
47        cout << v[i].id;
48        if (i + 1 < n) cout << " ";
49    }
50    cout << endl;
51
52    return 0;
53}

代码解释

• 结构体 Combo：为了方便地将总价、最大值、最小值、编号绑定在一起，我们使用结构体。你也可以用多个数组，但结构体会更清晰。
• 初始化 mx 和 mn：初始时将 mx 设为一个非常小的值（如 -1），mn 设为一个非常大的值（如 1e9），便于在遍历商品价格时用 max 和 min 函数正确更新。
• 比较函数 cmp：按题目要求的四级优先级排列，每一级都通过 if 判断，若不相等直接返回比较结果，相等则继续下一级。
• sort 函数：C++ 标准库的排序，需要 <algorithm> 头文件。v.begin() 和 v.end() 表示排序整个数组，cmp 为自定义规则。
• 输出格式：最后一个编号后不能有多余空格，因此用 if (i+1 < n) 判断是否输出空格。

时间复杂度分析

令 $n$ 为礼盒数量，$k$ 为每个礼盒中的商品数量。

• 读入数据并计算属性：$O(n \times k)$。
• 排序：调用 sort 对 $n$ 个元素排序，时间复杂度为 $O(n \log n)$。
• 输出：$O(n)$。

总时间复杂度 $O(nk + n \log n)$。在本题 $n \le 1000$、$k \le 10$ 的限制下，运行速度非常快，可以轻松通过。

空间复杂度 $O(n)$，仅需存储每个礼盒的四个整型信息。

总结

本题是一道典型的多关键字排序练习题，关键在于将礼盒的属性抽象成结构体，并按照题目给定的优先级编写正确的比较函数。对于 C++ 选手而言，熟练使用 sort 配合自定义比较函数是必须掌握的技能。如果使用其他语言（如 Python），同样可以用内置的排序函数配合 key 或 cmp_to_key 来实现，思路完全一致。