傳送門
https://pintia.cn/problem-sets/994805260223102976/problems/994805275146436608
題目
本題要求將給定的N個(gè)正整數(shù)按非遞增的順序捆姜，填入“螺旋矩陣”汰瘫。所謂“螺旋矩陣”，是指從左上角第1個(gè)格子開始伴栓，按順時(shí)針螺旋方向填充。要求矩陣的規(guī)模為m行n列雨饺，滿足條件：m*n等于N钳垮；m>=n；且m-n取所有可能值中的最小值额港。
輸入格式：
輸入在第1行中給出一個(gè)正整數(shù)N饺窿，第2行給出N個(gè)待填充的正整數(shù)。所有數(shù)字不超過10^4移斩，相鄰數(shù)字以空格分隔肚医。
輸出格式：
輸出螺旋矩陣绢馍。每行n個(gè)數(shù)字，共m行肠套。相鄰數(shù)字以1個(gè)空格分隔舰涌，行末不得有多余空格。
輸入樣例：
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
分析
我們先進(jìn)行題目分析你稚，先分解成一個(gè)個(gè)小問題瓷耙，然后逐個(gè)擊破：
1.先按倒序排列數(shù)組：
用algorithm里面的sort或者stdlib.h中的qsort都可以，但是qsort不能排vector刁赖，因?yàn)榈刂凡贿B續(xù)哺徊，這個(gè)要注意一下。要自己寫campare方法就行乾闰，默認(rèn)是升序的落追。
2.根據(jù)輸入的數(shù)組個(gè)數(shù)，求出矩陣的行數(shù)和列數(shù)：
這個(gè)方法有很多了涯肩，我用的就是對(duì)N開根的值開始轿钠，逐漸減到1，求m和n病苗，別的方法也行疗垛。
3.螺旋放置：
這個(gè)是難點(diǎn)，我開始聲明了變量status來確定是怎樣放置的硫朦，一共有四種：左->右贷腕，上->下，右->左咬展，下->上泽裳，然后針對(duì)不同的status對(duì)坐標(biāo)有相應(yīng)的自增或自減方法，并且如果這一行如果被放置過了破婆，要給放置的次數(shù)做減1的操作涮总。
注意：我想到的螺旋放置方法不適用于只有一列的情況，要單獨(dú)判斷這種情況祷舀，單獨(dú)寫輸出方法瀑梗。
源代碼
//C/C++實(shí)現(xiàn)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
bool compare(int a, int b){
return a > b; //desc
}
int main(){
int N;
scanf("%d", &N);
vector<int> v(N);
for(int i = 0; i < N; ++i){
scanf("%d", &v[i]);
}
//sort
sort(v.begin(), v.end(), compare);
//calculate m and n
int i = sqrt((double)N);
int m, n;
for(; i >= 1; --i){
if(N % i == 0){ //整除
n = i;
m = N / n;
break;
}
}
int a[m][n]; //一會(huì)改成a[m][n]
int x = 0, y = -1;
int status = 0; //從左向右是0，上向下是1裳扯，右向左是2抛丽，下向上是3
int c0 = 0, c1 = 0, c2 = 0, c3 = 0; //走過該路徑就自增1
if(n == 1){
for(int i = 0; i < v.size(); ++i){
printf("%d\n", v[i]);
}
}
else{
for(int i = 0; i < v.size(); ++i){
if(status == 0){
++y;
if(y == n - 1 - c1){
status = 1; //該從上往下填充了
++c0;
}
}
else if(status == 1){
++x;
if(x == m - 1 - c2){
status = 2; //該從右往左填充了
++c1;
}
}
else if(status == 2){
--y;
if(y == 0 + c3){
status = 3; //該從下往上填充了
++c2;
}
}
else if(status == 3){
--x;
if(x == 0 + c0){ //該從左往右填充了
status = 0;
++c3;
}
}
a[x][y] = v[i];
}
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(j == 0){
printf("%d", a[i][j]);
}
else{
printf(" %d", a[i][j]);
}
}
printf("\n");
}
}
return 0;
}
