pta甲级 1105 Spiral Matrix (25分)

链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805363117768704

题意：给你N个数，将其放入非递增的螺旋矩阵中，矩阵大小为m*n,要求：

1）N = m * n

2) m >= n

3) m-n最小

思路：按照走路+转向的思路，当碰壁（超出矩阵范围或已有值）就顺时针转向。

#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1e4+10; int mp[1100][1100]; int n,a[N],r,c; int nex[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; int main(void){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); r=sqrt(n); while(n%r) r++; c=n/r; if(r<c) swap(r,c); sort(a+1,a+1+n); int x=1,y=1,d=0; for(int i=n;i>=1;i--){ mp[x][y]=a[i]; int tx=x+nex[d][0],ty=y+nex[d][1]; if((tx<1||tx>r||ty<1||ty>c)||mp[tx][ty]) d=(d+1)%4; x+=nex[d][0]; y+=nex[d][1]; } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) printf("%d%c",mp[i][j],j==c?'\n':' '); return 0; }