G4024 [GESP202603 四级] 礼盒排序 题解

知识点：多关键字排序、统计、编号保留。

解题思路

每个礼盒统计总和sum、最大值hi、最小值lo，连同原编号组成四元组，按升序排序，输出原编号。

为什么正确

多关键字排序按先后级别比较，完整实现题面的逐级判定，编号作为最终平局规则。

易错点

必须保留原编号，排序后不能输出新下标；优先顺序是总和、最大值、最小值、编号。

复杂度

时间O(nk+n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<tuple<int,int,int,int>>a;
    for(int i=1;i<=n;i++) {
        int sum=0,lo=10001,hi=0;
        for(int j=0;j<k;j++) {
            int x;
            cin>>x;
            sum+=x;
            lo=min(lo,x);
            hi=max(hi,x);
        }
        a.emplace_back(sum,hi,lo,i);
    }
    sort(a.begin(),a.end());
    for(auto [sum,hi,lo,i]:a)cout<<i<<" ";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。