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

思路及注意点：来自《算法笔记》

AC代码：

//#include<iostream>
//#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
//#include<map>
//#include<cctype>
using namespace std;

const int maxn=10010;
//二维数组用于打印，一维数组用于输入 
int matrix[maxn][maxn],a[maxn];

bool cmp(int a,int b){
	return a>b;
}

int main()
{
	//输入 
	int N;
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d",&a[i]);
	}
	//排序
	sort(a,a+N,cmp); 
	//特殊情况：N=1
	if(N==1){
		printf("%d",a[0]);
		return 0;
	} 
    //确定m、n、四个边界 
	int m=(int)ceil(sqrt(1.0*N));//若不是整数则向上取整，因为m>=n 
	while(N%m!=0){  //若还不是约数 
		m++;  //找最小的能整除N的m，因为m-n要最小 
	} 
    //i、j是当前欲填的位置（一一对应，方便找规律），now是当前欲填的数的下标 
	int n=N/m,i=1,j=1,now=0; 
	int U=1,D=m,L=1,R=n;
	//螺旋填入二维数组Matrix
	while(now<N){
		//向右 
		while(now<N&&j<R){
			matrix[i][j]=a[now++]; 
			j++;
		}
		//向下
		while(now<N&&i<D){
			matrix[i][j]=a[now++];
			i++;
		} 
		//向左
		while(now<N&&j>L){
			matrix[i][j]=a[now++];
			j--;
		} 
		//向上 
		while(now<N&&i>U){
			matrix[i][j]=a[now++];
			i--;
		} 
		U++;D--;L++;R--;  //缩小边界 
		i++;j++;  //位置移至内层左上角 
		if(now==N-1){  //最后一个元素单独填入
			matrix[i][j]=a[now++];
		} 
	} 
	//输出matrix数组
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			printf("%d",matrix[i][j]);
			if(j<n) printf(" ");
			else printf("\n");
		}
	} 
//	system("pause");
	return 0;
}

总结：

1. 想要打印成矩阵的形式肯定要用二维数组，其中的值就用输入数组螺旋地填入，其中向左和向上原来可以倒着填，和倒着打印一维数组是一样的
2. 要学会将题目中的信息转化成精简的、有用的信息。原本m和n我还想暴力两层遍历，现在知道了若知道约数之间的关系，不妨先开根号，慢慢往上取较大者
3. 打印图形下标最好就从1开始，这样一一对应，也方便找规律