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<iostream>
#include<algorithm>
#include<vector>
#include<math.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;
}