一千题，No.0064（螺旋矩阵）

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

输入格式：

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

输出格式：

输出螺旋矩阵。每行 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

 解题思路：

按照题目硬求解，结果三个样例超时了

#include <bits/stdc++.h>

using namespace std;

int m,n;

void func(int a)
{
    for(int i = sqrt(a)+1;i >= 1;--i)
    {
        for(int j = i;j >= 1;--j)
        {
            if(i * j == a)
            {
                ::m = i;
                ::n = j;
                return;
            }
        }
    }
}

int main()
{
    multiset<int,greater<int>> s;
    int a;
    cin >> a;
    if(a == 1)
    {
        int num;
        cin >> num;
        cout << num;
        return 0;
    }
    else if(a == 0)
    {
        return 0;
    }

    func(a);
    while(a--)
    {
        int num;
        cin >> num;
        s.insert(num);
    }

    int arr[m][n];
    int check[m][n];
    memset(arr,0,sizeof(arr));
    memset(check,0,sizeof(check));
    pair<int,int> point = {0,0};
    auto t = s.begin();
    arr[0][0] = *t;
    check[0][0] = 1;
    ++t;
    while(t != s.end())
    {
        while(point.second+1 < n && t != s.end() && check[point.first][point.second+1] == 0)
        {
            arr[point.first][point.second+1] = *t;
            check[point.first][point.second+1] = 1;
            ++point.second;
            ++t;
        }
        while(point.first+1 < m && t != s.end() && check[point.first+1][point.second] == 0)
        {
            arr[point.first+1][point.second] = *t;
            check[point.first+1][point.second] = 1;
            ++point.first;
            ++t;
        }
        while(point.second-1 >= 0 && t != s.end() && check[point.first][point.second-1] == 0)
        {
            arr[point.first][point.second-1] = *t;
            check[point.first][point.second-1] = 1;
            --point.second;
            ++t;
        }
        while(point.first-1 >= 0 && t != s.end() && check[point.first-1][point.second] == 0)
        {
            arr[point.first-1][point.second] = *t;
            check[point.first-1][point.second] = 1;
            --point.first;
            ++t;
        }
    }

    for(int i = 0;i < m;++i)
    {
        for(int j = 0;j < n;++j)
        {
            if(j != 0) cout << " ";
            cout << arr[i][j];
        }
        cout << endl;
    }
    return 0;
}

后来把set排序改为vector，sort排序依然超时，果断打开柳s的代码，发现不是排序的问题，是m,n的取值函数耗时太大

附上柳s的代码：

for (n = sqrt((double)a); n >= 1; n--)
    {
        if (a % n == 0) {
            m = a / n;
            break;
        }
    }

c++代码如下：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    vector<int> v;
    int a;
    cin >> a;
    int m,n;
    for (n = sqrt((double)a); n >= 1; n--)
    {
        if (a % n == 0) {
            m = a / n;
            break;
        }
    }

    while(a--)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(),v.end(),greater<int>());

    int arr[m][n];
    int check[m][n];
    memset(arr,0,sizeof(arr));
    memset(check,0,sizeof(check));
    pair<int,int> point = {0,0};
    auto t = v.begin();
    arr[0][0] = *t;
    check[0][0] = 1;
    ++t;
    while(t != v.end())
    {
        while(point.second+1 < n && t != v.end() && check[point.first][point.second+1] == 0)
        {
            arr[point.first][point.second+1] = *t;
            check[point.first][point.second+1] = 1;
            ++point.second;
            ++t;
        }
        while(point.first+1 < m && t != v.end() && check[point.first+1][point.second] == 0)
        {
            arr[point.first+1][point.second] = *t;
            check[point.first+1][point.second] = 1;
            ++point.first;
            ++t;
        }
        while(point.second-1 >= 0 && t != v.end() && check[point.first][point.second-1] == 0)
        {
            arr[point.first][point.second-1] = *t;
            check[point.first][point.second-1] = 1;
            --point.second;
            ++t;
        }
        while(point.first-1 >= 0 && t != v.end() && check[point.first-1][point.second] == 0)
        {
            arr[point.first-1][point.second] = *t;
            check[point.first-1][point.second] = 1;
            --point.first;
            ++t;
        }
    }

    for(int i = 0;i < m;++i)
    {
        for(int j = 0;j < n;++j)
        {
            if(j != 0) cout << " ";
            cout << arr[i][j];
        }
        cout << endl;
    }
    return 0;
}