螺旋矩阵 (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}