个人练习-PAT甲级-1105 Spiral Matrix

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

题目大意，给出一串序列，要求将其按顺时针顺序填入一个m*n的矩阵中，其中m>n且m-n最小。

简单题，只需要注意顺时针这个顺序即可。先求m和n。

    m = (int)(sqrt(1.0*N));while (N % m != 0) {
    m++;}n = N / m;if (m < n) {
    int tmp = m;m = n;n = tmp;}

p和q表示下一个填入矩阵的位置，限定p和q的上下限，用dir表示指针移动的方向。

    int p = 0, q = 0, pos = N-1, dir = 1;int pmin = 1, pmax = m-1, qmin = 0, qmax = n-1;while (pos != -1) {
    mat[p][q] = arr[pos--];if (dir == 1) {
    if (q < qmax) q++;else {
    qmax--; p++; dir = 2;}}else if (dir == 2) {
    if (p < pmax) p++;else {
    pmax--; q--; dir = 3;}}else if (dir == 3) {
    if (q > qmin) q--;else {
    qmin++; p--; dir = 4;}}else {
    if (p > pmin) p--;else {
    pmin++; q++; dir = 1;}}}

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>using namespace std;vector<int> arr;
int mat[102][102];
int N, m, n;int main() {
    scanf("%d", &N);arr.resize(N);for (int i = 0; i < N; i++) {
    scanf("%d", &arr[i]);}sort(arr.begin(), arr.end());m = (int)(sqrt(1.0*N));while (N % m != 0) {
    m++;}n = N / m;if (m < n) {
    int tmp = m;m = n;n = tmp;}int p = 0, q = 0, pos = N-1, dir = 1;int pmin = 1, pmax = m-1, qmin = 0, qmax = n-1;while (pos != -1) {
    mat[p][q] = arr[pos--];if (dir == 1) {
    if (q < qmax) q++;else {
    qmax--; p++; dir = 2;}}else if (dir == 2) {
    if (p < pmax) p++;else {
    pmax--; q--; dir = 3;}}else if (dir == 3) {
    if (q > qmin) q--;else {
    qmin++; p--; dir = 4;}}else {
    if (p > pmin) p--;else {
    pmin++; q++; dir = 1;}}}for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
    if (j != 0)printf(" ");printf("%d", mat[i][j]);if (j == n-1)printf("\n");}}return 0;
}