按四级关键字给礼盒排序:总价 → 最贵商品 → 最便宜商品 → 编号,输出礼盒编号。
每个礼盒包含 k 件商品。请按以下规则给礼盒排序,输出排序后的礼盒编号:
多关键字排序结构体 + 比较函数总和/最大值/最小值
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、k;随后 n 行每行 k 个价格 |
| 输出 | 排序后的礼盒编号(从 1 开始),空格分隔 |
| 数据范围 | n ≤ 1000,k ≤ 10 |
| 价格范围 | 1 ≤ 价格 ≤ 10⁴ |
| 排序键 | 总价 → 最高价 → 最低价 → 编号 |
先把每个礼盒的三个统计量算出来。
| 编号 | 商品价格 | 总价 sum | 最贵 mx | 最便宜 mn |
|---|---|---|---|---|
| 1 | 3 5 2 | 10 | 5 | 2 |
| 2 | 4 1 5 | 10 | 5 | 1 |
| 3 | 2 2 4 | 8 | 4 | 2 |
| 4 | 3 4 3 | 10 | 4 | 3 |
3 号总价 8 最小 → 排在第一个
其余三个总价都是 10,需要进入下一级比较
确定第一个:3 号
1 号 mx = 5
2 号 mx = 5
4 号 mx = 4
4 号的 4 最小 → 排在第二位
确定第二个:4 号(mx = 4)
1 号 mn = 2
2 号 mn = 1
总价、最贵都相同,只能比最低价
2 号的 1 更小 → 排在第三位
确定第三个:2 号(mn = 1)
只剩 1 号一个,直接排在最后
✅ 最终顺序 3 4 2 1
| 编号 | 价格 | sum | mx | mn |
|---|---|---|---|---|
| 1 | 2 3 | 5 | 3 | 2 |
| 2 | 3 2 | 5 | 3 | 2 |
把四个键存进结构体,写 cmp 按顺序比较
if (a.sum != b.sum) return a.sum < b.sum;,依次往下写四个 if,最后一个直接返回编号比较。比如 key = sum×1000 + mx×100 + ...
| 方案 | 代码量 | 可维护性 |
|---|---|---|
| 结构体 + cmp | 约 25 行 | ⭐⭐⭐⭐⭐ |
| 压成单键 | 约 15 行(含位设计) | ⭐⭐ |
第一行输入 n 和 k,随后 n 行每行 k 个价格,程序会按四级关键字排序。
点按钮开始 →
#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 级的编号比较,在四项全相同时排序结果不稳定。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 3 | 3 4 2 1 | 题面样例 |
1 2 | 1 | 只有一个礼盒 |
2 2 | 1 2 | 统计量完全相同,靠编号决胜 |
3 1 | 2 3 1 | k = 1 时 sum = mx = mn |
2 2 | 1 2 | 完全相同的数据,编号升序 |
需要存 n 个结构体,每个含 4 个整数。
✅ n 只有 1000,任何排序实现都瞬间完成。
// 多关键字排序的通用写法 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,其余保持不变即可,每个关键字可以独立选择升降序。)