关于c++:PAT甲级1105-Spiral-Matrix

题目粗心

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

算法思路

此题的求解步骤分为求解矩阵规模和填充矩阵

• 1、求解矩阵规模
  因为须要行和列都尽可能的相近，所以初始取 col 为根号 n，只有 $n $%$ col != 0$,col 就递加，从而获取列 col 和行 row。
• 2、填充矩阵

这里采纳设置矩阵的 4 个边界(左右高低), 别离为 $left=0,right=col-1,up=0,bottom=row-1$，依照从左到右，从上到下，从右到左，从下到上的程序顺次填充，每一次填充结束就更新边界，比方依照从左往右填充了一行就更新上边界 up(++up)，只有每次填充结束后,index>=n，阐明填充完结。

提交后果

AC 代码

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; ++i) {scanf("%d", &a[i]);
    }
    sort(a, a + n, [&](int a, int b) {return a > b;});
    // 计算 m 和 n
    int col = (int) sqrt(n * 1.0);
    while (n % col != 0) {--col;}
    int row = n / col;
    int result[row][col];
    int index = 0;// 标记以后填充的元素
    // 定义数组的左右高低边界
    int left = 0, right = col - 1, up = 0, bottom = row - 1;
    while (index < n) {
        // 从左到右
        for (int i = left; i <= right; ++i) {result[up][i] = a[index++];
        }
        // 更新上界
        ++up;
        if (index >= n) break;
        // 从上到下
        for (int i = up; i <= bottom; ++i) {result[i][right] = a[index++];
        }
        // 更新右边界
        --right;
        if (index >= n) break;
        // 从右到左
        for (int i = right; i >= left; --i) {result[bottom][i] = a[index++];
        }
        // 更新下界
        --bottom;
        if (index >= n) break;
        // 从下到上
        for (int i = bottom; i >= up; --i) {result[i][left] = a[index++];
        }
        // 更新左边界
        ++left;
    }
    for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {printf("%d", result[i][j]);
            if (j < col - 1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}