【PAT甲级】1105 Spiral Matrix (25分)

题意：
输入一个正整数N（实则<=1e5），接着输入一行N个正整数（<=1e4）。降序输出螺旋矩阵。

trick：

测试点1，3运行超时原因：直接用sqrt(N)来表示矩阵的宽会在N是素数时出错，直接扫一遍找一个最大因子即可，简单粗暴。

AAAAAccepted code：

 1 #define HAVE_STRUCT_TIMESPEC
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int a[100007];
 5 int ans[1007][1007];
 6 int main(){
 7     ios::sync_with_stdio(false);
 8     cin.tie(NULL);
 9     cout.tie(NULL);
10     int n;
11     cin>>n;
12     for(int i=1;i<=n;++i)
13         cin>>a[i];
14     int y=0;
15     for(int i=1;i*i<=n;++i)
16         if(n%i==0)
17             y=i;
18     int x=n/y;
19     sort(a+1,a+1+n);
20     int top=1,bottom=x,left=1,right=y;
21     int temp=n;
22     int flag=1;
23     while(temp){
24         if(flag==1){
25             for(int i=left;i<=right;++i)
26                 ans[top][i]=a[temp--];
27             ++top;
28             flag=2;
29         }
30         else if(flag==2){
31             for(int i=top;i<=bottom;++i)
32                 ans[i][right]=a[temp--];
33             --right;
34             flag=3;
35         }
36         else if(flag==3){
37             for(int i=right;i>=left;--i)
38                 ans[bottom][i]=a[temp--];
39             --bottom;
40             flag=4;
41         }
42         else if(flag==4){
43             for(int i=bottom;i>=top;--i)
44                 ans[i][left]=a[temp--];
45             ++left;
46             flag=1;
47         }
48     }
49     for(int i=1;i<=x;++i){
50         for(int j=1;j<=y;++j){
51             cout<<ans[i][j];
52             if(j<y)
53                 cout<<" ";
54         }
55         if(i<x)
56             cout<<"\n";
57     }
58     return 0;
59 }