5057: 螺旋矩阵

描述

 

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

输入

 

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

输出

 

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

样例输入

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

 

#include <bits/stdc++.h>
using namespace std;
int n,m,num,jishu;
int arr[1010][1010];
vector<int> vec;
bool cmp(int a,int b){
    return a>b;
}
int main()
{
    cin>>num;
    for(int i=sqrt(num);i>=1;i--){
        if(num%i==0){
            n=max(num/i,i);
            m=min(num/i,i);
            break;
        }
    }
    for(int i=1,d;i<=num;i++){
        cin>>d;
        vec.push_back(d);
    }
    sort(vec.begin(),vec.end(),cmp);
    int t=n/2+n%2;
    jishu=0;
    for(int i=0;i<t;i++){
        for(int j=i;j<=m-i-1&&jishu<num;j++){
            arr[i][j]=vec[jishu++];
        }
        for(int j=i+1;j<=n-i-1&&jishu<num;j++){
            arr[j][m-i-1]=vec[jishu++];
        }
        for(int j=m-i-2;j>=i&&jishu<num;j--){   //不实现
            arr[n-i-1][j]=vec[jishu++];
        }
        for(int j=n-i-2;j>=i+1&&jishu<num;j--){
            arr[j][i]=vec[jishu++];
        }
    }
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++){
        if(j!=0) cout << " ";
        cout << arr[i][j];
        if(j==m-1){
            cout << endl;
        }
    }
    return 0;
}