PAT甲级A1105---快乐模拟

1105 Spiral Matrix (25分)

分析：

将N个数逆时针螺旋填入矩阵中，由于行数m * 列数n 要等于N，所以m为N的约数。又m≥n，且m-n最小，可以先令m等于根号N，然后往上找第一个N的约数。
令U,D,L,R代表上下左右四个边界，i,j代表正在填充的行数和列数，每填充完一层之后，就令边界缩小1个数，然后把i和j加到下一层第一个数继续填充。
注意特判N等于1时，直接输出。如果只剩最后中间一个数时，也要输出。

C++：

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 100010;
int A[maxn];
int matrix[maxn][maxn];

bool cmp(int a, int b) {
    return a > b;
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    if (N == 1) {
        printf("%d", A[0]);
        return 0;
    }
    sort(A, A + N, cmp);
    int m = ceil(sqrt(1.0 * N));
    while (N % m != 0) {
        m++;
    }
    int n = N / m, i = 1, j = 1, now = 0;
    int U = 1, D = m, L = 1, R = n;//4个边界
    while (now < N) {
        while (now < N && j < R) {
            matrix[i][j] = A[now++];
            j++;
        }
        while (now < N && i < D) {
            matrix[i][j] = A[now++];
            i++;
        }
        while (now < N && j > L) {
            matrix[i][j] = A[now++];
            j--;
        }
        while (now < N && i > U) {
            matrix[i][j] = A[now++];
            i--;
        }
        U++, D--, L++, R--;
        i++, j++;
        if (now == N - 1) {
            matrix[i][j] = A[now++];
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d", matrix[i][j]);
            if (j < n) {
                printf(" ");
            } else {
                printf("\n");
            }
        }
    }
    return 0;
}