C程序-PAT-1050 螺旋矩阵

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

输入格式：

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

输出格式：

输出螺旋矩阵。每行 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;
}