立志用更少的代碼做更高效的表達(dá)

---

Pat乙級(jí)最優(yōu)化代碼+題解+分析匯總——>傳送門

---

本題要求將給定的 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

---

解題思路

1、求出行數(shù)和列數(shù)。 我的思路是：求出該值的平方差，從平方差遞減，用num分別除以這些數(shù)字， 一旦可以整除， 一定為最靠近平方差的一組數(shù)， 也就是行數(shù)-列數(shù)為最小值。

2、定義優(yōu)先隊(duì)列，將數(shù)據(jù)輸入，降序排列

3、將螺旋矩陣分為四部分，循環(huán)輸入數(shù)據(jù)。如圖所示， 期間，需要不斷的修正i和j的值。

代碼看似復(fù)雜， 但邏輯很清晰， 只需分成上述三個(gè)部分， 第三部分再分為四個(gè)小部分， 分模塊看即可。

---

代碼展示

#include<bits/stdc++.h> using namespace std; int main() {int x; cin>>x;int sq = sqrt(x);int m, n; //m行n列 while(sq) { //第一部分：求出行數(shù)和列數(shù) if(x%sq == 0) {m = sq; n = x / sq;break;} else {sq--;}}if(m < n) swap(m, n); //使m保持最大 int a[m][n] = {0}, mm = m, nn = n;priority_queue<int, vector<int>, less<int> >q;//第二部分：定義降序的優(yōu)先隊(duì)列存放數(shù)據(jù) for(int i = 0; i < x; i++) {int num; cin>>num;q.push(num);}//第三部分：構(gòu)造螺旋矩陣int i1 = 0, j1 = 0;while(!q.empty()) { //當(dāng)隊(duì)列非空時(shí)一直循環(huán) int n1 = n; while(n1-- > 0 && !q.empty()) { a[i1][j1] = q.top();q.pop();j1++;} j1--; i1++;n--;m--;int m1 = m;while(m1-- > 0 && !q.empty()) {a[i1][j1] = q.top();q.pop();i1++;}i1--; j1--;m--;int n2 = n;while(n2-- > 0 && !q.empty()) {a[i1][j1] = q.top();q.pop();j1--;}j1++; i1--;n--;int m2 = m;while(m2-- > 0 && !q.empty()) {a[i1][j1] = q.top();q.pop();i1--;} i1++; j1++;}for(int i = 0; i < mm; i++) {for(int j = 0; j < nn; j++) {if(j != 0) cout << ' ';cout << a[i][j];}cout << '\n';}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【最全解析】1050 螺旋矩阵 (25分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。