一、技术总结
- 题意是,给定N个数字,然后要使得生成一个m x n的矩阵,同时m>=n;保证他们之间相差最小,数字要从大到小顺时针进行填充进入矩阵。
- 对于输入数字,使用cmp比较函数进行排序,同时使用vector进行存储。
- 具体形式如下图:
- 由上图知道,我们分析得出,m可以这样求出,用N开根号得到不超过这个数的最大整数a,然后再使用N去除以a,如果可以整除那么就得出了m,如果不能够,就让a一直减减,知道可以整除。
- 求出m后,我们看到上图,分析外层循环的层数,如果m是奇数level=m/2 + 1;如果m是偶数level=m/2,所以level = m / 2 + m % 2;
- t是用来保证,矩阵被填充完后就结束。
- 接下来就是分析内部的四层循环了,以第一层为例,首先是最上面一侧,可以发现是矩阵的n在变化,而m没有变化,所以j = i;j <= n - 1 - i && t < N - 1; j++ a[i][j],然后分析最右侧,发现矩阵数m在变化,n没有变,所以j = i + 1; j <= m - 2 - i && t < N - 1; j++ a[j][n - 1 - i],接下来分析最下侧,发现矩阵n在变化,而m没有发生变化,所以j = n - 1 - i; j >= i && t < N - 1; j-- a[m - 1 - i][j],最后分析最左侧, 发现是m在变化,n没有发生变化,所以j = m - 2 - i; j >= i && t < N - 1; j-- a[j][i]
二、参考代码:
#include<bits/stdc++.h>
using namespace std;
int cmp(int a, int b){
return a > b;
}
int main(){
int N, m, n, t = 0;
scanf("%d", &N);
for(n = sqrt((double)N); n >= 1; n--){
if(N % n == 0){
m = N / n;
break;
}
}
vector<int> a(N);
for(int i = 0; i < N; i++){
scanf("%d", &a[i]);
}
sort(a.begin(), a.end(), cmp);
vector<vector<int> > b(m, vector<int>(n));
int level = m / 2 + m % 2;
for(int i = 0; i < level; i++){
for(int j = i; j <= n - 1 - i && t <= N - 1; j++){
b[i][j] = a[t++];
}
for(int j = i + 1; j <= m - 2 - i && t <= N - 1; j++){
b[j][n - 1 - i] = a[t++];
}
for(int j = n - i - 1; j >= i && t <= N - 1; j--){
b[m - 1 - i][j] = a[t++];
}
for(int j = m - 2 - i; j >= i + 1 && t <= N - 1; j--){
b[j][i] = a[t++];
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
printf("%d", b[i][j]);
if(j != n - 1) printf(" ");
}
printf("\n");
}
return 0;
}