PAT (Basic Level) Practice （中文） 1050 螺旋矩阵 (25 分)
题目描述
本题要求将给定的 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
题目要求：
作者 CHEN, Yue
单位 浙江大学
代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB
解题思路：
// 1、我们需要得到 螺旋矩阵 的行 row 与列 col 的值。
可以算出 n 的所有因子，然后找差值最小的两个因子。// 求出所有因子再计算差值有些复杂。
// 考虑到 相差最小的因子一定在 n 的平方根附近 若 n 是一个平方数，很明显最小差值的因子就是它的平方根
例如： n = 16 时，此时的 row = col = sqrt(n)
// 若 n 不是一个平方数，则从 n 的算术平方根 n0 开始往下枚举，枚举到 n 的一个因子的时候，即可得到符合题意的
// col 和 row 的值
例如： n = 10 时，sqrt(10) = 3 (因为col和row都是整型数据，自动取整) ，
但是 3 不是 10 的因子，所以往下枚举 2 ， 2 是 10 的因子， 所以满足要求的 row = 5 ，col = 2 ( row >= col )
// 2、保存输入的 length 为 n 的数组，并从大到小排序
// 这里就是基础的 sort 函数运用了 ，存好数组，要求从大到小排序；手写一个与 sort 函数配合的 cmp 即可。
bool cmp(int a , int b){
return a > b ;
}
sort(array,array + array.length() , cmp) ;
// 我就是不想写 cmp 函数怎么办呢？ 简单！
// 从大到小排序，我们知道，sort 函数是默认从小到大排序的，我把从小到大的数组，“倒”过来，不就是从大到小啦
sort(array,array + array.length()) ;
reverse(array,array + array.length()) ;
// 3、准备工作做好了，剩下就是怎么将数组里的数，按照螺旋矩阵的要求，给我螺旋进一个二维数组了。
// 数组中有 n 个数要填入螺旋矩阵，所以结束的标志很容易想到是，记录填入了 x 个数，当 x < n 的时候，说明还要填。
int ans[10010][110] = { 0 } , array[10010] ;
int i = 0 , j = 0 , x = 0 ; // i 和 j 表示此时填的位置。
while( x < n ){
// 按照要求，先是从左往右填，所以是 i 保持不变 j 和 x 每次自增 1
/*
划重点，j < col 容易，因为最多也只有 col 列，为啥还需要 ans[i][j] == 0 呢？
因为，我们知道，如果 ans[i][j] 的值是 0 ，那么此时一定没有被前面某圈的螺旋矩阵填入数据，
反之，则这个位置已经被写入数据了，所以就不能继续此次赋值操作了，因为会覆盖以前的数据。
*/
while( j < col && ans[i][j] == 0)
ans[i][j++] = array[x++] ;
// 将需要的位置 拉回到下一起点。
j -- ;
i ++ ;
// 右边 从上往下填， j 不变， i 和 x 自增
while( i < row && ans[i][j] == 0)
ans[i++][j] = array[x++] ;
// 将需要的位置 拉回到下一起点。
j -- ;
i -- ;
// 下边 从右往左填， i 不变， j 自减 ， x 自增
while( i < row && ans[i][j] == 0)
ans[i][j--] = array[x++] ;
// 将需要的位置 拉回到下一起点。
j ++ ;
i -- ;
// 左边 从下往上填， j 不变， i 自减 ， x 自增
while( i < row && ans[i][j] == 0)
ans[i--][j] = array[x++] ;
// 将需要的位置 拉回到下一起点。
j ++ ;
i ++ ;
}
// 4、螺旋矩阵的输出，二维矩阵的输出，那就不是问题了
for(int i = 0 ; i < r ; i++){
cout << ans[i][0] ;
for(int j = 1 ; j < c ; j++){
cout<<" "<<ans[i][j] ;
}
cout<<endl ;
}
完整代码：
#include<bits/stdc++.h>
using namespace std ;
int ans[10010][110]={0} , num[100010] ;
int n ;
bool cmp(int a , int b){
return a > b ;
}
int main(){
cin >> n ;
for(int i = 0 ; i < n ; i++){
cin >> num[i] ;
}
sort(num , num + n , cmp) ;
int n0 = sqrt(n) , r = 1 , c , x = 0 ;// r为行，c为列
for(int i = n0 ; i >= 1 ; i--){
if(n % i == 0){
r = i ;
break ;
}
}
c = n / r ;
if(r < c) swap(r , c);
int i = 0 , j = 0 ;
while(x < n){
// 从左往右填
while( j < c && ans[i][j] == 0)
ans[i][j++] = num[x++] ;
j-- ;//调整下一条边的起点
i++ ;
// 右边从上往下填
while( i < r && ans[i][j] == 0)
ans[i++][j] = num[x++] ;
i-- ;//调整下一条边的起点
j-- ;
// 下边从右往左填
while( j >= 0 && ans[i][j] == 0)
ans[i][j--] = num[x++] ;
i-- ;//调整下一条边的起点
j++ ;
//从下往上填
while(i >= 0 && ans[i][j] == 0)
ans[i--][j] = num[x++] ;
i++ ;//调整为下一回合起点
j++ ;
}
for(int i = 0 ; i < r ; i++){
cout << ans[i][0] ;
for(int j = 1 ; j < c ; j++){
cout<<" "<<ans[i][j] ;
}
cout<<endl ;
}
return 0 ;
}