题目描述

给定一个包含 N 个正整数的序列，请你将序列中的元素以非递增顺序填充到螺旋矩阵中。

从左上角的第一个元素开始填充，并按照顺时针方向旋转。

要求矩阵有 m 行 n 列，并且 m,n 满足：

m × n = N
m ≥ n
m − n 尽可能小

思路

1、首先根据条件，用试除法解出绝对值相差最小的R(行)，C(列) 这里判断m >= n的办法是只用试到n / i就可以

2、然后从大到小排序 以满足从大到小填充的条件

3、按照 AcWing 756 蛇形矩阵 的填充方法 利用 l r top bottom 四个变量 来表示 这个矩形的边界.

具体为:

用 l 指向待输出部分的最左侧，r 指向待输出部分的最右侧，top 指向待输出部分的最上侧，bottom

指向待输出部分的最下侧。

循环指向：

1. 从左到右构造最上侧的一行，待出去部分的最上侧下移，然后top + 1。

2. 从上到下构造最右侧的一列，待输出部分的最右侧左移，然后r - 1。

3. 从右到左构造最下方的一行，待输出部分的最下侧上移，然后bottom - 1。

4. 从下到上构造最右侧的一列。待输出部分的最左侧右移。然后l + 1。

[此处参考Hasity的题解解释]

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110, M = 1e4 + 10, inf = 0x3fffffff;

int g[N][N];
int a[M];
int n;

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

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    //将数组从大到小排序
    sort(a, a + n, cmp);

    int min = inf, R, C;
    //试除法求矩阵的行R列C
    for(int i = 1; i <= n / i; ++ i ){
        if(n % i == 0){
            int t = n / i, k = i;
            if(abs(t - k) < min) {
                min = abs(t - k);
                R = t, C = k;    
            }
        }
    }

    //四个边界
    int k = 0, l = 1, r = C, top = 1, bottom = R;

    while(l <= r && top <= bottom)
    {
        for(int i = l; i <= r; i ++ ) g[top][i] = a[k ++];
        for(int i = top + 1; i <= bottom; i ++ ) g[i][r] = a[k ++];
        //在mn不相等的时候中间一圈数据会覆盖掉出错 必须加上top < bottom l < r
        for(int i = r - 1; i >= l && top < bottom; i -- ) g[bottom][i] = a[k ++];
        for(int i = bottom - 1; i > top && l < r; i -- ) g[i][l] = a[k ++];
        l ++, r --, top ++, bottom --;
    }
    for(int i = 1; i <= R; i ++ ){
        for(int j = 1; j <= C; j ++ )
            cout << g[i][j] << " ";
        puts("");
    }
    return 0;
}