|
本题要求将给定的 N 个正整数按非递增的顺序，填入“螺旋矩阵”。所谓“螺旋矩阵”，是指从左上角第 1 个格子开始，按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列，满足条件：m×n 等于 N；m≥n；且 mn 取所有可能值中的最小值。
输入格式：
输入在第 1 行中给出一个正整数 N，第 2 行给出 N 个待填充的正整数。所有数字不超过 104，相邻数字以空格分隔。
输出格式：
输出螺旋矩阵。每行 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
思路：确定m，n；对数据进行排序；将数据填充如二维数组（关键部分）
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
const int M=10000;
int main( )
{
int arr[M];
int a[M][100];//注意大小必须是M，例：当是接近M的素数时
int N,i,j,n,m;
scanf("%d",&N);
m=n=sqrt(N);//开方
//m*n 等于 N；m>=n；且 m-n 取所有可能值中的最小值。
while(1)//
{
if(n*m==N)
break;
if(n*m>N)//乘积大于N则n自减
n--;
else if(n*m<N)//乘积大于N则m自加
m++;
}
for(i=0;i<N;i++)
{
scanf("%d",&arr[i]);
}
sort(arr,arr+N);//排序
int x=0,y=-1,t=0;
for(i=N-1;i>=0;)
{
//从最外层开始填充，t代表层数，同时必须有i>=0，否则当n=1时会出错
while(y+1<n-t&&i>=0) a[x][++y]=arr[i--];//填充上
while(x+1<m-t&&i>=0) a[++x][y]=arr[i--];//填充右
while(y-1>=t&&i>=0) a[x][--y]=arr[i--];//填充下
t++;
//填充左，从下往上填充，不能覆盖最顶上数据，所以t++在上一行
while(x-1>=t&&i>=0) a[--x][y]=arr[i--];
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%d",a[i][j]);
if(j<n-1)
printf(" ");
}
printf("\n");
}
return 0;
}
| 
转播
