文章目录

• 前言
• 题目
• 二、解法
• AC答案
• 总结

---

前言

今天练习了一下Pat1105题，第一眼看着有点奇怪，主要是spiral这个单词一时间忘记了有点尴尬，根据样例发现就是一道模拟题，虽然模拟题一般挺简单的，但是对于我好像，比一般算法题错还容易错。。

---

提示：以下是本篇文章正文内容，下面案例可供参考

题目

1105 Spiral Matrix (25 分)
This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order. A spiral matrix is filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has m rows and n columns, where m and n satisfy the following: m×n must be equal to N; m≥n; and m−n is the minimum of all the possible values.

Input Specification:

Each input file contains one test case. For each case, the first line
gives a positive integer N. Then the next line contains N positive
integers to be filled into the spiral matrix. All the numbers are no
more than 10 4 . The numbers in a line are separated by spaces.

Output Specification:

For each test case, output the resulting matrix in m lines, each
contains n numbers. There must be exactly 1 space between two adjacent
numbers, and no extra space at the end of each line.

Sample Input:

12 37 76 20 98 76 42 53 95 60 81 58 93

Sample Output:
98 95 93
42 37 81
53 20 76
58 60 76

二、解法

本题要求螺旋式按照输入数组从大到小输出一个m x n 的矩阵，要求矩阵m - n 要最小，很简单想到求因式分解，求其差值最小，很简单就是从给定X的开平方项递减循环。

for(int i = sqrt(x); i >0 ; i--){
		//当第一次x % 1==0 时则得到差值最小的因式分解
        if(x % i == 0){
            m = x / i;
            n = i;
            break;
        }
    }
    //m为行， n为列

然后要求数组从大到小输出，那么就需要对输入的数组进行排序，直接用stl 的快排就行了。

// 注意sort 默认时从小到大， 可以自定义个比较器改一下，这里仍使用默认，后面会解释
sort(q,  q + x);

在数组排序后，将数组螺旋输出为m x n 的矩阵，其实只要按照从左 -> 右 -> 下 -> 上 按一个循环去给矩阵赋值，同时由于从外向内循环，所以需要不断更新左右上下的边界（建议画一个图模拟一下矩阵i，j坐标的变化，很快就能找到边界变化规律）

int up = 0, down = m - 1, left = 0, right = n -1;
    int i = 0, j = 0;
    //由于我采用的是sort的默认排序，所以排序后是从小到大的，则对螺旋矩阵赋值时要从后往前扶赋值到矩阵，cnt = x -1（最大值开始）
    int cnt = x - 1;
    while( cnt >= 0 ){
    	//不取j <= right 这样可以保证同一循环内的各方向的更新次数是相同的，边界管理更加简单一些。
        while( j < right && cnt >= 0){
            res[i][j++] = q[cnt--]; 
        }
        while( i < down && cnt >= 0){
            res[i++][j] = q[cnt--];
        }
        while( j > left && cnt>= 0){
            res[i][j--] = q[cnt--];
        }
        while( i> up && cnt >= 0){
            res[i--][j] = q[cnt--];
        }
        //边界的更新最好画一个图用样例模拟一次就好理解了
        right --;
        down --;
        left ++;
        up ++;
        i++,j++;
        //当cnt == 0 的直接操作，不进入下一循环，避免下一循环特殊情况可能存在的问题，因为去除此代码，测试点2过不去
        if( cnt == 0){
            res[i][j] = q[cnt--];
        }
    }

最后有一个小坑，就是需要对 N = 1的情况要单独处理，否则测试点4会过不去。

    if(x == 1){
        printf("%d", q[0]);
        return 0;
    }

AC答案

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int x , m , n;
int main(){
    scanf("%d", &x);
    int q[x];
    for(int i = 0; i< x; i++){
        scanf("%d", &q[i]);
    }
    if(x == 1){
        printf("%d", q[0]);
        return 0;
    }
    for(int i = sqrt(x); i >0 ; i--){
        if(x % i == 0){
            m = x / i;
            n = i;
            break;
        }
    }
    int res[m][n];
    sort(q, q + x);
    int up = 0, down = m - 1, left = 0, right = n -1;
    int i = 0, j = 0;
    int cnt = x - 1;
    while( cnt >= 0 ){
        while( j < right && cnt >= 0){
            res[i][j++] = q[cnt--]; 
        }
        while( i < down && cnt >= 0){
            res[i++][j] = q[cnt--];
        }
        while( j > left && cnt>= 0){
            res[i][j--] = q[cnt--];
        }
        while( i> up && cnt >= 0){
            res[i--][j] = q[cnt--];
        }
        right --;
        down --;
        left ++;
        up ++;
        i++,j++;
        if( cnt == 0){
            res[i][j] = q[cnt--];
        }
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(j == 0){
                printf("%d",res[i][j]);
            }else{
                printf(" %d",res[i][j]);
            }
        }
        puts("");
    }

    return 0;
}

总结

模拟题本身不难，一般情况下按照样例画出图模拟一遍就可以知道一般思路，注意点就是要小心特殊情况（比如 N = 1 等等）。加油吧！