解题思路

这道题要求学生按编号站好方阵后，再做“行列互换”（数学上叫转置）。

1. 学生原来怎么站？

学生从 1 开始编号，按行站成 n×n 方阵。所以第 r 行第 c 列站的是 (r-1)×n+c 号学生。

比如 n=4 时：

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

2. 行列互换是什么？

老师喊“行列互换”，第 i 行第 j 列的学生要站到第 j 行第 i 列。所以新的方阵第 i 行第 j 列，放的其实是原来第 j 行第 i 列的学生，也就是 (j-1)×n+i 号。

3. 对照样例

还是 n=4，新方阵第 1 行第 2 列 = 原来第 2 行第 1 列 = (2-1)×4+1=5；第 3 行第 4 列 = 原来第 4 行第 3 列 = (4-1)×4+3=15。和样例完全一样！所以根本不用真的开数组，直接用公式输出就行。

参考代码

#include <iostream>
using namespace std;
int main(){
    // P4523 行列互换：学生1~n*n按行站成方阵，互换后行变列、列变行（转置）
    // 原方阵第 r 行第 c 列的学生编号是 (r-1)*n+c
    // 转置后第 i 行第 j 列就放原来第 j 行第 i 列的学生
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout << (j-1)*n + i; // 转置后的编号
            if(j<n) cout << " "; // 两个数字之间用空格隔开
        }
        cout << endl;            // 每行结束换行
    }
    return 0;
}

复杂度分析

方阵有 n 行 n 列，共 n² 个格子，每个格子直接算编号并输出，所以时间复杂度是 O(n²)。题目保证 3<n<10，最多 9×9=81 个数字，很快。

程序只用了两个循环变量和一个 n，没有开数组，空间复杂度是 O(1)。