A20826. 礼盒排序
填空题
较难
知识点
题目描述
礼盒排序
题目描述
商店推出了许多礼盒，每个礼盒中包含K件商品，每件商品都有一个价格。
现在需要对这些礼盒进行排序，排序规则如下：
1. 先按礼盒总价格从小到大排序；
2. 如果总价格相同，按礼盒中最贵商品的价格从小到大排序；
3. 如果仍然相同，按礼盒中最便宜商品的价格从小到大排序；
4. 如果仍然相同，按礼盒编号从小到大排序。 请输出排序后的礼盒编号。
输入格式
第一行包含两个整数n和k，分别表示礼盒数量和每个礼盒中商品的数量。
接下来 行，每行包含 k个整数，第 i行表示第 i个礼盒中各商品的价格。
输出格式
输出一行，包含排序后的礼盒编号（编号从1 开始），用空格分隔。
样例
输入样例
4 3
3 5 2
4 1 5
2 2 4
3 4 3输出样例
3 4 2 1 样例解释
4 个礼盒分别为：
| 编号 | 商品价格 | 总价 | 最大值 | 最小值 |
| 1 | 352 | 10 | 5 | 2 |
| 2 | 415 | 10 | 5 | 1 |
| 3 | 224 | 8 | 4 | 2 |
| 4 | 343 | 10 | 4 | 3 |
排序过程：
1. 按总价排序，3号礼盒总价最小；
2. 其余总价均为 10，再按最大值排序，4号最大值更小；
3. 1号和2号最大值相同，再按最小值排序，2号更小。
最终顺序为：3 4 2 1
数据范围
保证1≤n≤103,1≤k≤10,商品价格≤104。
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Combo {
int sum, mx, mn, id;
};
bool cmp(const Combo &a, const Combo &b) {
if (a.sum != b.sum) return a.sum < b.sum;
if (a.mx != b.mx) return a.mx < b.mx;
if (a.mn != b.mn) return a.mn < b.mn;
return a.id < b.id;
}
int main() {
int n, k;
cin >> n >> k;
vector<Combo> v(n);
for (int i = 0; i < n; i++) {
v[i].sum = 0;
v[i].mx = -1;
v[i].mn = 1e9;
v[i].id = i + 1;
for (int j = 0; j < k; j++) {
int x;
cin >> x;
v[i].sum += x;
v[i].mx = max(v[i].mx, x);
v[i].mn = min(v[i].mn, x);
}
}
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < n; i++) {
cout << v[i].id;
if (i + 1 < n) cout << " ";
}
cout << endl;
return 0;
}
上一题
下一题