PAT甲级1105.

目录

A1105

题目

样例

输入:

12
37 76 20 98 76 42 53 95 60 81 58 93

输出:

98 95 93
42 37 81
53 20 76
58 60 76

思路和坑点

　　按照从大到小的方法，以螺旋矩阵的格式输出数组。首先需要确定螺旋矩阵的规模m*n，由于满足m>=n且m和n尽可能的接近，所以从n的开方考虑，m和n必在其开方数值的两侧。
　　然后使用快速排序对数组进行排序。按照螺旋矩阵输出时，每次填充一层，不妨从外到内依次编号，从0层开始，也对应了每一层开始时的位置。每次按照先上方从左到右，右侧从上到下，下方从右到左，左侧从下到上的顺序进行填充，使用r，l记录每一个元素在矩阵中的位置，每层填充完毕后矩阵规模减小一层。并且需要检查是否在某行填充完毕后整个矩阵已经成型的情况，因为可能内部中心只有一层。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(void)
{
    int N;
    cin>>N;
    vector<int> v(N);
    for(int i=0;i<N;i++){
        cin>>v[i];
    }
    int m,n;
    for(int i=sqrt((float)N);i>=1;i--){         //m,n一定是分布在n开方附近的两个数，且m>=n 
        if(N%i==0){
            m=N/i;n=i;break;                    //如果找到一个满足的矩阵大小规模，结束循环 
        }
    }
    sort(v.begin(),v.end());                    //排序 
    int size=v.size();                            
    int index=size-1;                            
    vector<vector<int> > vc(m,vector<int> (n)); //创建一个二维数组 
    int Mt=m,Nt=n,cnt=0;                        //Mt，Nt表示内部小矩阵的规模，cnt是计数器，一旦装填完毕就结束循环 
    for(int i=0;;i++,Mt--,Nt--){                //没填满一个外层，矩阵规模减小，i表示当前层数，起始为0 
        int r,l;                                //r，l表示每次填充的坐标，r表示行，l表示列 
        for(r=i,l=i;l<Nt;l++){                  //上方从左到右按行填充，l递增 
            vc[r][l]=v[index--];cnt++;            
        }    
        if(cnt==size) break;
        
        for(l--,r++;r<Mt;r++){                  //右侧按照列填充，需要将上一轮l循环边界多加的1减去，然后r递减 
            vc[r][l]=v[index--];cnt++;
        }    
        if(cnt==size) break;
        
        for(l--,r--;l>=i;l--){                  //下方按行从右往左填充 
            vc[r][l]=v[index--];cnt++;
        }
        if(cnt==size) break;
        
        for(l++,r--;r>=i+1;r--){                //左侧从下往上填充 
            vc[r][l]=v[index--];cnt++;
        }    
        if(cnt==size) break;                    //如果有任何一次填充过程中，元素全部装填完毕则结束循环 
    }
    for(int i=0;i<m;i++)                        //输出矩阵结果 
        for(int j=0;j<n;j++){
            if(j) putchar(' ');
                cout<<vc[i][j];
            if(j==n-1)
                cout<<'\n';
        }
    
    return 0;
}