題目鏈接：點擊查看

題目大意：給出N個數，降序排序后構造螺旋矩陣，要求行n和列m滿足要求n*m==N并且n>m并且(m-n)盡可能小

題目分析：排序后就是簡單的蛇形填數了，網上都是用一個while套四個while的寫法，我還是喜歡用走迷宮的寫法來寫，這個題有個很關鍵的一點，就是數組大小，因為題目保證了所有數字都在1e4之內，但是如果我們要開1e4*1e4的矩陣，是肯定開不下的，這樣直接交上去會有一個測試樣例T掉，那我們該怎么辦呢？有一個很關鍵的信息，就是n>m，并且(m-n)盡可能小，那么我們可以分析一下，當N最大取到1e4時，肯定將n和m分為sqrt(1e4)=100最為合適，但當N是一個大于100的質數時，此時只能分為(N,1)，這是兩種比較極端的情況了，到這里我們可以發現，m的值最大只能達到100，而n的值最大才可能達到1e4，所以我們開始組的時候就可以直接開maze[1e4][1e2]，而不是maze[1e4][1e4]了，真的是學到了，因為這個細節調了有半個小時的代碼，總是T掉，原來是數組開太大的原因

不得不說這個題目的數據也是專門卡這個點的，就看能不能想到了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<deque> #include<unordered_map> #define Pi acos(-1.0) using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;const int b[4][2]={0,1,1,0,0,-1,-1,0};int n,m;int a[N];bool cmp(int a,int b) {return a>b; }void getnm(int x) {int mark;for(int i=1;i<=sqrt(x);i++)if(x%i==0)mark=i;m=mark;n=x/mark; }int maze[N][100];bool vis[N][100];bool check(int x,int y) {if(x<0||y<0||x>=n||y>=m)return false;if(vis[x][y])return false;return true; }int main() { // freopen("input.txt","r",stdin);int N;scanf("%d",&N);for(int i=1;i<=N;i++)scanf("%d",a+i);sort(a+1,a+1+N,cmp);getnm(N);int cnt=1;maze[0][0]=a[cnt++];vis[0][0]=true;int x=0,y=0;int pos=0;while(cnt<=N){int xx=x+b[pos][0];int yy=y+b[pos][1];while(check(xx,yy)){maze[xx][yy]=a[cnt++];vis[xx][yy]=true;x=xx;y=yy;xx=x+b[pos][0];yy=y+b[pos][1];}pos=(pos+1)%4;}for(int i=0;i<n;i++){cout<<maze[i][0];for(int j=1;j<m;j++)cout<<' '<<maze[i][j];cout<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的PAT (Basic Level) 1050 螺旋矩阵(模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。