螺旋矩阵 (PATB-1050)

题面

本题要求将给定的 N 个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“螺旋矩阵”,是指从左上角第 1 个格子开始,按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列,满足条件:m×n 等于 N;m≥n;且 m−n 取所有可能值中的最小值。

输入

输入在第 1 行中给出一个正整数 N,第 2 行给出 N 个待填充的正整数。所有数字不超过 10^4,相邻数字以空格分隔。

输出

输出螺旋矩阵。每行 n 个数字,共 m 行。相邻数字以 1 个空格分隔,行末不得有多余空格。

样例输入

112
237 76 20 98 76 42 53 95 60 81 58 93

样例输出

198 95 93
242 37 81
353 20 76
458 60 76

提示

思路

代码

 1const int mxn = 1e5 + 5;
 2int a[mxn], ans[mxn];
 3
 4int main()
 5{
 6    int t; scanf("%d", &t);
 7
 8    int n, m;
 9    for(int i=sqrt(t); i; i--){
10        if(t%i == 0){
11            m = i;
12            n = t/m;
13            break;
14        }
15    }
16    for(int i=0; i<t; i++)
17        scanf("%d", &a[i]);
18    sort(a, a+t);
19
20    int x=0, y=-1;
21    for(t--; t>=0;)
22    {
23        while(y+1<m && *(ans+x*m+y+1) == 0){
24            ++y; *(ans+x*m+y) = a[t--];
25        }
26
27        while(x+1<n && *(ans+(x+1)*m+y) == 0){
28            ++x; *(ans+x*m+y) = a[t--];
29        }
30
31        while(y-1>=0 && *(ans+x*m+y-1) == 0){
32            --y; *(ans+x*m+y) = a[t--];
33        }
34
35        while(x-1>=0 && *(ans+(x-1)*m+y) == 0){
36            --x; *(ans+x*m+y) = a[t--];
37        }
38    }
39
40    for(int i=0; i<n; i++)
41    {
42        for(int j=0; j<m; j++)
43        {
44            if(j) printf(" ");
45            printf("%d", *(ans+i*m+j));
46        }
47        printf("\n");
48    }
49
50    return 0;
51}