PAT乙级1050 || 螺旋矩阵（详解，C/C++示例，测试点分析）

Posted on In

螺旋矩阵

题目描述

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

输入格式

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

输出格式

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

输入样例

1
2
12
37 76 20 98 76 42 53 95 60 81 58 93

输出样例

1
2
3
4
98 95 93
42 37 81
53 20 76
58 60 76

问题解决

解题思想

由于所有的数据都不超过$10^4$，矩阵的行数m不小于列数n，故列数n不超过100，因此把螺旋矩阵定义为：a[9999][100]。

对于一个正整数N，找到两个正整数m和n，满足：m×n 等于 N；m≥n；且 m−n取所有可能值中的最小值。可知m在sqrt(N)的右侧，n在sqrt(N)左侧，只需从1到sqrt(N)枚举出使得N / i - i最小的i。

确定螺旋矩阵的行数和列数后，只需向里面填数就行。先将N个数降序排列，然后从第一个数开始沿着螺旋矩阵的第0行开始向左填到最左侧（注意终止条件，终止时填到了第n - 1列），接着沿着第n - 1行向下填到最下段（终止时填到了第m - 1行），接着沿着第m - 1行向右填到最右侧（终止时填到第0列），接着沿着第0列向上填到最上端未填处（终止时填到第1行，因第0行已经填过了），重复上述过程，逐渐向中心收缩直到没有未填的位置为止。

代码示例（C/C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int Calc_m(int N);
bool cmp(int a, int b) {
    return a > b;
}
int a[9999][100] = {0}, b[10000];  //a[][]存入螺旋矩阵数据（注意此处位置，为什么不能放到main里面）
int main() {
    int N;
    scanf("%d",&N);
    int m, n;
    m = Calc_m(N);
    n = N / m;
    for(int i = 0; i < N; i++) {
        scanf("%d",&b[i]);
    }
    sort(b,b + N,cmp);    //降序排序
    a[0][0] = b[0]; //先把第一个数赋给螺旋矩阵
    int i = 0, j = 0, k = 0;    //i,j 为螺旋矩阵的行列下标，k为输入数据的下标
    while(k < m * n - 1) {  //注意此处为什么不是while(k < m * n)
        while(j + 1 < n && !a[i][j + 1]) {  //向右
            a[i][++j] = b[++k];
        }
        while(i + 1 < m && !a[i + 1][j]) {  //向下
            a[++i][j] = b[++k];
        }
        while(j - 1 >= 0 && !a[i][j - 1]) { //向左
            a[i][--j] = b[++k];
        }
        while(i - 1 >= 0 && !a[i - 1][j]) { //向上
            a[--i][j] = b[++k];
        }
    }
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++){
            printf("%d",a[i][j]);
            if(j != n - 1){
                printf(" ");
            }
        }
        printf("\n");
    }
    return 0;
}
//满足m * n = N 且m >= n,m - n的值最小的m
int Calc_m(int N) {
    int m, maxn = 9999;    //m与n的差值初始化为可能的最大值maxn
    for(int i = 1; i <= sqrt(N * 1.0); i++) {
        if(N % i == 0) {
            if(N / i - i < maxn) {
                maxn = N / i - i;
                m = N / i;
            }
        }
    }
    return m;
}

题目来源：PAT乙级1050
作者：CHEN, Yue
单位：浙江大学

稀罕作者