1050 螺旋矩阵(25)（25 分）

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

输入格式：

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

输出格式：

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

PS：

这道题在《信息学奥赛》上有（我没有抄！那几个while的部分是在监视窗口一步步调试修正),这里用vector创建动态数组 ，跟其他人的代码没多大区别，所以这道题就不细说思路了，不懂的话可以直接找我0.0，另外还做了一些简化。

注意：需要使用动态数组（测试点7）

#include<iostream>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

int main() {

	int a[10000];

	int N, m, n;

	cin >> N;

	for (int i = sqrt(N) + 1; i > 0; i--)

		if (N%i == 0) {

			m = i; n = N / i; break;

		}

	if (m < n)  swap(m, n);    //保证m>n;

	vector<vector<int>>b(m + 1);   //使用vector创建二维动态数组（第1行第1列为了方便理解不使用）

	for (int i = 0; i <= m; i++)

		b[i].resize(n + 1);

	for (int i = 0; i < N; i++)

		cin >> a[i];

	sort(a, a + N, greater<int>());    //降序排序

	int i = 1, j = 0, count = 0;

	while (N!=count) {

		while (j < n&&b[i][j + 1] == 0) b[i][++j] = a[count++];

		while (i < m&&b[i + 1][j] == 0)b[++i][j] = a[count++];

		while (j > 1 && b[i][j - 1] == 0)b[i][--j] = a[count++];

		while (i > 1 && b[i - 1][j] == 0)b[--i][j] = a[count++];

	}

	for (int i = 1; i <= m; i++) {

		cout << b[i][1];

		for (int j = 2; j <= n; j++)

			cout << " " << b[i][j];

		cout << endl;

	}

	return 0;

}