PAT 乙级 1050 螺旋矩阵(解题思路+AC代码)
题目:
本题要求将给定的 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
代码长度限制 16 KB
时间限制 200 ms
内存限制 64 MB
解题思路
-
首先确定m行n列,m和n需要满足3个条件:m*n=N;m>=n;m-n要最小。一个数的平方根-平方根为最小,但是m和n为正整数,所以可以使用sqrt函数求出一个整数平方根向下取整的值,并用N来除以这个数,如果余数为0,那么令n为这个数,m为N除以n的数;如果余数不为0,那么n–,然后继续循环判断。这样可以保证m-n为最小,也就是最靠近平方根的一组数。
-
使用STL中的优先队列,将数据输入并降序排序。
-
将螺旋矩阵的最外层分为四部分,并放入一个二维数组中,倒数第二层也是一样的思路,所以可以用一个循环。最后打印这个二维数组即可。
AC代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
//1.找到m和n
int N = 0;
cin >> N;
int m = 0, n = 0;
int tmp = sqrt(N);
while (tmp)
{
if (N % tmp == 0)
{
n = tmp;
m = N / n;
break;
}
else
{
tmp--;
}
}
//2.输入数据并降序排列
priority_queue<int, vector<int>, less<int>> q;
for (int i = 0; i < N; i++)
{
int num;
cin >> num;
q.push(num);
}
//3.构造螺旋矩阵
int a[m][n] = {0}, mm = m, nn = n;
int i1 = 0, j1 = 0;
while (!q.empty())
{
int n1 = n;
while (n1-- && !q.empty())
{
a[i1][j1] = q.top();
q.pop();
j1++;
}
j1--;
i1++; m--;
int m1 = m;
while (m1-- && !q.empty())
{
a[i1][j1] = q.top();
q.pop();
i1++;
}
i1--;
j1--;n--;
int n2 = n;
while (n2-- && !q.empty())
{
a[i1][j1] = q.top();
q.pop();
j1--;
}
j1++;
i1--;m--;
int m2 = m;
while (m2-- && !q.empty())
{
a[i1][j1] = q.top();
q.pop();
i1--;
}
i1++;
j1++;n--;
}
//4.打印螺旋矩阵
for (int i = 0; i < mm; i++)
{
for (int j = 0; j < nn; j++)
{
if (j != 0)
{
cout << " ";
}
cout << a[i][j];
}
cout << endl;
}
return 0;
}