欢乐赛#54 T5 题解 100% AC

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

int mp[110][110]; // 定义二维数组存储方阵数据（预留+10防止越界）

int main() {
    int n, m;
    cin >> n >> m; // 输入行列数
    
    // 读取原始方阵数据
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> mp[i][j];
    
    // 列处理（每列代表一个班级）
    for(int j = 1; j <= m; j++) {
        vector<int> c; // 临时存储非零身高数据
        
        // 收集当前列非零数据（过滤空位）
        for(int i = 1; i <= n; i++)
            if(mp[i][j] != 0) c.push_back(mp[i][j]);
        
        sort(c.begin(), c.end()); // 升序排序（$O(k\log k)$，k为该列人数）
        
        // 重新填充当前列（保持原有非零位置结构）
        int x = 0;
        for(int i = 1; i <= n; i++)
            if(mp[i][j] != 0) mp[i][j] = c[x++];
    }
    
    // 输出格式化结果
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++)
            cout << setw(4) << mp[i][j]; // 固定4字符宽度输出
        cout << endl;
    }
    return 0;
}

算法核心解析

1. 列优先处理：将每列视为独立班级，满足题目"每列一个班"的要求
2. 零值保留机制：
   • 用vector过滤存储非零值（if(mp[i][j]!=0)）
   • 排序后按原非零位置回填（保持空缺位置不变）
3. 时间复杂度：$O(m \times n \log n)$，其中主要开销来自每列的排序操作

关键步骤说明

1. 数据读取阶段：

   • 使用双重循环存储$n \times m$矩阵
   • 行列索引从1开始（符合题目描述习惯）

2. 排序处理阶段：

   • 对每列单独建立临时数组c存储有效身高
   • sort()默认升序排列，满足"前低后高"要求
   • 回填时通过x指针确保有序数据覆盖原非零位

3. 输出格式化：

   • setw(4)保证输出对齐（包括数字和零值空格）
   • 严格保持原始矩阵的行列结构

示例演算

以样例输入为例：

6 4
186 188 163 142
139 141 151 0
...（略）...

处理第1列时：

1. 收集非零值[186, 139, 142, 169, 200]
2. 排序得[139, 142, 169, 186, 200]
3. 按原非零位置回填，得到输出首列[139, 142, 169, 186, 200, 0]

该实现完美满足题目所有要求：

• 保持列结构不变
• 正确处理空位（零值）
• 输出格式严格对齐
• 在给定数据范围内高效运行