GESP 题解库 / 4 级题解 / [GESP202603 四级] 礼盒排序 · 第 1 / 25 题
GESP202603 四级 · B4502 · 简单

礼盒排序

按四级关键字给礼盒排序:总价 → 最贵商品 → 最便宜商品 → 编号,输出礼盒编号。

📊
n ≤ 1000
礼盒数
📦
k ≤ 10
每盒商品数
⚡
O(n log n)
时间复杂度
🎯
多关键字排序
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

每个礼盒包含 k 件商品。请按以下规则给礼盒排序,输出排序后的礼盒编号:

  1. 先按礼盒总价格从小到大
  2. 总价相同则按最贵商品价格从小到大
  3. 还相同则按最便宜商品价格从小到大
  4. 仍相同则按礼盒编号从小到大
💡
人话翻译:这是一种"多关键字排序"。思路很固定:把四个比较关键字都算出来存进结构体,然后写一个比较函数,按优先级依次比较。第 4 条用编号兜底,保证不会出现"分不出先后"的情况。

🔍 关键词提取

多关键字排序结构体 + 比较函数总和/最大值/最小值

已知条件

项目说明
输入第一行 n、k;随后 n 行每行 k 个价格
输出排序后的礼盒编号(从 1 开始),空格分隔
数据范围n ≤ 1000,k ≤ 10
价格范围1 ≤ 价格 ≤ 10⁴
排序键总价 → 最高价 → 最低价 → 编号

需要解决的问题

02
思维导图
整理解题思路的全貌
📦 四级关键字排序
📥 读入统计
读 n、k
每行读 k 个价格
同时算 sum/mx/mn
编号从 1 开始
🧮 四个键
sum:盒内总价
mx:最贵商品
mn:最便宜商品
id:礼盒编号
⚖️ 比较顺序
先比 sum 小者优先
再比 mx 小者优先
再比 mn 小者优先
最后比 id 小者优先
📤 输出
排序后只输出编号
空格分隔
行末不加空格
n ≤ 1000 用 sort 即可
03
样例手算推导
样例 4 个礼盒的四级比较过程

🧮 样例:4 个礼盒逐级比较

先把每个礼盒的三个统计量算出来。

编号商品价格总价 sum最贵 mx最便宜 mn
13 5 21052
24 1 51051
32 2 4842
43 4 31043
1
第 1 级:比总价

3 号总价 8 最小 → 排在第一个

其余三个总价都是 10,需要进入下一级比较

确定第一个:3 号

2
第 2 级:比最贵商品

1 号 mx = 5

2 号 mx = 5

4 号 mx = 4

4 号的 4 最小 → 排在第二位

确定第二个:4 号(mx = 4)

3
第 3 级:比最便宜商品

1 号 mn = 2

2 号 mn = 1

总价、最贵都相同,只能比最低价

2 号的 1 更小 → 排在第三位

确定第三个:2 号(mn = 1)

4
第 4 级:比编号

只剩 1 号一个,直接排在最后

✅ 最终顺序 3 4 2 1

🔑
样例里其实没用到第 4 级(前三级就分完了),但编码时必须写上——否则遇到"四个键全相同"的两个礼盒时,排序结果不确定,可能随机出错。用唯一标识(如编号)兜底,是多关键字排序的标准做法。

🧮 一组会用到第 4 级的数据

编号价格summxmn
12 3532
23 2532
💡
两个礼盒的三项统计量完全一样,此时只能比编号:1 号排在 2 号前面。如果没有第 4 级,排序结果就不确定了。
04
解法对比
结构体 + 比较函数 vs 编码成单个数值

⚔️ 解法对比

🟢 结构体 + 比较函数(推荐) 推荐

把四个键存进结构体,写 cmp 按顺序比较

  • 时间 O(n log n × k)
  • 逻辑与题面一一对应
  • 新增关键字只需加一行
  • 不易出错
💡
比较函数模板:if (a.sum != b.sum) return a.sum < b.sum;,依次往下写四个 if,最后一个直接返回编号比较。

🟠 把多键压成一个整数

比如 key = sum×1000 + mx×100 + ...

  • 需要精心设计进制
  • 容易发生溢出或位重叠
  • 价格范围变化就要改
  • 可读性差
⚠️
注意:压成一个数确实能直接 sort,但本题四个键的取值范围不同(总价可达 10⁵),很难选一个安全的进制,不推荐。

📈 性能对比

方案代码量可维护性
结构体 + cmp约 25 行⭐⭐⭐⭐⭐
压成单键约 15 行(含位设计)⭐⭐
05
算法流程图
统计 → 排序 → 输出编号
开始读入 n、ki 从 1 到 n:读入 k 个价格,算出 sum、mx、mn,记下编号 i按 (sum, mx, mn, id) 依次比较并排序输出排序后的编号序列结束还有礼盒 → 继续统计
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📦 礼盒排序器

第一行输入 n 和 k,随后 n 行每行 k 个价格,程序会按四级关键字排序。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

struct Box {
    int id;        // 礼盒编号(从 1 开始)
    int sum;       // 总价
    int mx;        // 最贵商品
    int mn;        // 最便宜商品
};

// 四级比较:越靠前的关键字优先级越高
bool cmp(const Box &a, const Box &b) {
    if (a.sum != b.sum) return a.sum < b.sum;   // 1. 总价小者优先
    if (a.mx != b.mx)   return a.mx  < b.mx;    // 2. 最贵商品小者优先
    if (a.mn != b.mn)   return a.mn  < b.mn;    // 3. 最便宜商品小者优先
    return a.id < b.id;                          // 4. 编号小者优先
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    vector<Box> v(n);
    for (int i = 0; i < n; i++) {
        v[i].id = i + 1;
        int sum = 0, mx = 0, mn = 100000;
        for (int j = 0; j < k; j++) {
            int p;
            scanf("%d", &p);
            sum += p;
            if (p > mx) mx = p;
            if (p < mn) mn = p;
        }
        v[i].sum = sum; v[i].mx = mx; v[i].mn = mn;
    }

    sort(v.begin(), v.end(), cmp);

    for (int i = 0; i < n; i++) {
        if (i) printf(" ");
        printf("%d", v[i].id);
    }
    printf("\n");
    return 0;
}
🔑
比较函数为什么能保证正确性?sort 要求比较函数满足"严格弱序":即 cmp(a,b) 为真表示 a 应排在 b 前面。我们按优先级依次比较,第一次出现差异的关键字就决定了顺序,这正是多关键字排序的本质。

📖 关键几行怎么看

代码作用为什么这样写
struct Box打包四个键四个字段一起参与比较,代码清晰
if (a.sum != b.sum) return ...逐级比较只有相等时才进入下一级,用 != 判断不等
return a.id < b.id;兜底保证排序结果唯一确定
mn = 100000初始化最小值价格 ≤ 10⁴,用大数初始化最稳
⚠️
两个坑:① 比较函数写成 a.sum <= b.sum,违反严格弱序会导致 sort 行为未定义(可能崩溃);② 忘了第 4 级的编号比较,在四项全相同时排序结果不稳定。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4 3
3 5 2 / 4 1 5 / 2 2 4 / 3 4 3
3 4 2 1题面样例
1 2
5 5
1只有一个礼盒
2 2
2 3 / 3 2
1 2统计量完全相同,靠编号决胜
3 1
9 / 5 / 7
2 3 1k = 1 时 sum = mx = mn
2 2
1 1 / 1 1
1 2完全相同的数据,编号升序
✅
自查清单:① 四个键都算了吗?② 比较用严格小于吗?③ 最后按编号兜底了吗?

🚨 易错点清单

⚠️
比较函数用了 <=:必须用严格小于,否则 sort 的行为未定义。
⚠️
漏掉编号兜底:四项完全相同时顺序不确定,不同编译器/不同数据集可能给出不同结果。
⚠️
最小值初始化为 0:价格都是正整数,用 0 初始化 mn 会导致 mn 永远为 0。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n × k)
空间复杂度
O(n)
n 最大
1000
k 最大
10

时间怎么算的?

空间都用在哪?

需要存 n 个结构体,每个含 4 个整数。

✅ n 只有 1000,任何排序实现都瞬间完成。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 多关键字排序的通用写法
struct Node { int a, b, c, id; };

bool cmp(const Node &x, const Node &y) {
    if (x.a != y.a) return x.a < y.a;    // 第一关键字
    if (x.b != y.b) return x.b < y.b;    // 第二关键字
    if (x.c != y.c) return x.c < y.c;    // 第三关键字
    return x.id < y.id;                   // 唯一标识兜底
}

// 用 lambda 写法(C++11 起)
sort(v.begin(), v.end(), [](const Node &x, const Node &y) {
    if (x.a != y.a) return x.a < y.a;
    if (x.b != y.b) return x.b < y.b;
    return x.id < y.id;
});

// 只有两个关键字时可以用 pair / tuple 直接排序
vector<pair<int,int>> p;   // 默认先比 first 再比 second
sort(p.begin(), p.end());

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
多关键字排序逐级比较直到分出胜负排行榜、成绩排序、优先级队列
唯一标识兜底用编号/下标保证顺序确定所有需要"稳定确定"的排序
结构体打包把相关字段放一起数据建模、图论建图
🌟
思考题:如果题目改成"总价从大到小,但最贵商品价格从小到大"(升降序混合),比较函数该怎么改?(提示:把第一条改成 a.sum > b.sum,其余保持不变即可,每个关键字可以独立选择升降序。)