#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool cmp(int a, int b){ return a > b; } int N, m, n; vector<int> num; int main(void){ cin >> N; for(int i = 0; i < N; i++){ int temp; cin >> temp; num.push_back(temp); } sort(num.begin(), num.end(), cmp); int min_mn = 9999; for(int i = 1; i <= N / i; i++){ if(N % i == 0 && N / i - i < min_mn){ n = i; m = N / i; min_mn = m - n; } } int juZhen[m][n]; //边界收缩法 int top = 0, right = n - 1, button = m - 1, left = 0; //此时应该存入的数的下标 int k = 0; while(k < N){ //右 for(int i = left; i <= right; i++){ juZhen[top][i] = num[k++]; } top++; //下 for(int i = top; i <= button; i++){ juZhen[i][right] = num[k++]; } right--; //左 for(int i = right; i >= left; i--){ juZhen[button][i] = num[k++]; } button--; //上 for(int i = button; i >= top; i--){ juZhen[left][i] = num[k++]; } left++; } for(int i = 0; i < m; i++){ for(int j = 0; j < n;j++){ cout << juZhen[i][j]; if(j != n - 1){ cout << " "; } } if(i != m - 1){ cout << endl; } } return 0; }本题要求将给定的 N 个正整数按非递增的顺序，填入“螺旋矩阵”。所谓“螺旋矩阵”，是指从左上角第 1 个格子开始，按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列，满足条件：m×n 等于 N；m≥n；且 m−n 取所有可能值中的最小值。 输入格式： 输入在第 1 行中给出一个正整数 N，第 2 行给出 N 个待填充的正整数。所有数字不超过 10 4 ，相邻数字以空格分隔。 输出格式： 输出螺旋矩阵。每行 n 个数字，共 m 行。相邻数字以 1 个空格分隔，行末不得有多余空格。

<think>根据用户需求，我们需要将给定的N个正整数按非递增顺序（即递减）填充到一个m行n列的螺旋矩阵中，并满足： 1. m × n = N 2. m ≥ n 3. m-n的值尽可能小（即取所有可能值中的最小值） 步骤： 1. 对输入的N个正整数进行非递增排序（即从大到小排序）。 2. 确定矩阵的行数m和列数n：由于m×n=N，且m≥n，m-n最小。我们可以从sqrt(N)开始向下找n，这样m=N/n（取整），并确保m≥n且m*n=N。实际上，我们遍历n从floor(sqrt(N))到1，第一个满足N%n==0的n即为所求，然后m=N/n，此时m-n最小（因为n是小于等于sqrt(N)的最大因子）。 3. 初始化一个m行n列的矩阵（二维数组）。 4. 按照顺时针螺旋方向（从左上角开始，向右→向下→向左→向上）填充排序后的数组。 填充螺旋矩阵的思路： - 定义四个边界：上边界top=0，下边界bottom=m-1，左边界left=0，右边界right=n-1。 - 初始化一个索引index=0，指向排序后数组的当前元素。 - 按照顺时针方向，依次填充上边界（从左到右）、右边界（从上到下）、下边界（从右到左）、左边界（从下到上），每填充完一条边界，就将该边界向内收缩（如top++，right--等），直到所有元素填充完毕（即index达到N-1）。 注意：由于填充方向是顺时针，且我们每次填充一个完整的边界，然后缩小边界，直到所有元素填充完成。 C++实现步骤： 1. 输入正整数N，然后输入N个正整数。 2. 对N个正整数进行排序（从大到小）。 3. 计算m和n：寻找满足条件的n（从sqrt(N)向下取整开始递减，直到找到第一个能被N整除的数n，则m=N/n）。 4. 初始化一个m行n列的二维数组（全0）。 5. 设置边界和当前填充方向（实际上我们可以用四个循环模拟四个方向）。 6. 循环填充，直到所有数字都被填入。 代码结构： - 排序：使用sort并传入greater<int>()实现降序排序。 - 计算m和n：从sqrt(N)向下取整开始，递减寻找n，使得N%n==0，则n即为所求列数，m=N/n。 - 初始化二维数组：vector<vector<int>> matrix(m, vector<int>(n))。 - 填充螺旋矩阵：使用四个变量（top, bottom, left, right）表示当前边界，以及一个变量index表示当前填充到第几个数字（从0开始）。 循环条件：index < N 1. 从左到右填充上边界（top行，从left到right），填充后top++。 2. 从上到下填充右边界（right列，从top到bottom），填充后right--。 3. 从右到左填充下边界（bottom行，从right到left），填充后bottom--。 4. 从下到上填充左边界（left列，从bottom到top），填充后left++。 注意：每次填充一个方向后，需要检查index是否达到N（避免重复填充或越界），同时每次填充一个方向后，边界会变化，需要检查边界是否有效（例如，在填充右边界时，需要确保top<=bottom，否则可能已经填充完了）。 但是，在边界收缩的过程中，可能会出现单行或单列的情况，所以每一步填充后都要检查是否还有未填充的位置。 具体代码实现： ```cpp #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { int N; cin >> N; vector<int> nums(N); for (int i = 0; i < N; i++) { cin >> nums[i]; } // 非递增排序（从大到小） sort(nums.begin(), nums.end(), greater<int>()); // 计算m和n int n = (int)sqrt(N); while (N % n != 0) { n--; } int m = N / n; // 注意：题目要求m>=n，且m-n最小，这样找到的n是小于等于sqrt(N)的最大因子，所以m>=n满足，且m-n最小。 // 初始化矩阵 vector<vector<int>> matrix(m, vector<int>(n)); // 螺旋填充 int top = 0, bottom = m - 1, left = 0, right = n - 1; int index = 0; // 当前填充的数字在nums中的索引 while (index < N) { // 从左到右填充上边界 for (int i = left; i <= right && index < N; i++) { matrix[top][i] = nums[index++]; } top++; // 从上到下填充右边界 for (int i = top; i <= bottom && index < N; i++) { matrix[i][right] = nums[index++]; } right--; // 从右到左填充下边界 for (int i = right; i >= left && index < N; i--) { matrix[bottom][i] = nums[index++]; } bottom--; // 从下到上填充左边界 for (int i = bottom; i >= top && index < N; i--) { matrix[i][left] = nums[index++]; } left++; } // 输出矩阵 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cout << matrix[i][j]; if (j < n - 1) cout << " "; } cout << endl; } return 0; } ``` 注意：在计算m和n时，我们假设了N是完全平方数或者有因子，所以从sqrt(N)向下取整开始找，一定能找到n（因为n=1时，m=N，一定能整除）。 但是，这里有一个细节：题目要求m>=n，且m-n最小。我们这样找n（从sqrt(N)向下取整开始递减）得到的n是小于等于sqrt(N)的最大因子，因此m=N/n>=n，且m-n最小（因为n越大，m就越小，m-n就越小？实际上，我们是要让m-n最小，即m和n尽可能接近。所以从sqrt(N)向下取整开始找第一个整除的n，这样n是小于等于sqrt(N)的最大因子，那么m=N/n>=sqrt(N)，所以m-n最小。例如，N=20，sqrt(20)≈4.47，向下取整为4，20%4=0，所以n=4，m=5，m-n=1。而如果取n=2，m=10，m-n=8，显然1<8，所以正确。 但是，还有一种情况：如果N是质数，那么n=1，m=N。 测试：输入N=12，则n从3开始（sqrt(12)≈3.46，向下取整3），12%3=0，所以n=3，m=4，m-n=1。 所以，上述计算m和n的代码正确。 填充螺旋矩阵时，我们使用四个方向的循环，每次循环都检查index是否达到N，避免多填。 最后，输出矩阵。 注意：题目要求按非递增顺序，所以排序时使用降序排序，然后从大到小填充。 但是，螺旋矩阵的填充顺序是固定的（顺时针），而填入的数字是从大到小，所以第一个填入的是最大的数，在矩阵的左上角。 相关问题： 1. 如何确定螺旋矩阵的边界条件以避免重复填充？ 2. 如果要求按递增顺序填充螺旋矩阵，代码需要做哪些调整？ 3. 螺旋矩阵还有哪些应用场景？</think>### C++实现螺旋矩阵填充 #### 解决思路 1. **输入处理**：读取正整数N和N个整数 2. **排序**：将数字按非递增排序（从大到小） 3. **确定矩阵尺寸**： - 计算满足 $m \times n = N$ 且 $m \ge n$ 的矩阵行列数 - 使 $m - n$ 的值最小化 4. **螺旋填充**： - 使用四指针法（上、下、左、右边界） - 按顺时针方向填充：右→下→左→上 - 每完成一圈收缩边界 #### 完整代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { // 输入数据 int N; cin >> N; vector<int> nums(N); for (int i = 0; i < N; i++) { cin >> nums[i]; } // 非递增排序 sort(nums.begin(), nums.end(), greater<int>()); // 计算矩阵尺寸 (m×n=N, m≥n, m-n最小) int n = sqrt(N); while (N % n != 0) n--; int m = N / n; // 初始化矩阵 vector<vector<int>> matrix(m, vector<int>(n, 0)); // 四指针定义边界 int top = 0, bottom = m - 1; int left = 0, right = n - 1; int index = 0; // 当前填充位置 // 螺旋填充核心逻辑 while (index < N) { // 向右填充 (上边界) for (int i = left; i <= right && index < N; i++) matrix[top][i] = nums[index++]; top++; // 向下填充 (右边界) for (int i = top; i <= bottom && index < N; i++) matrix[i][right] = nums[index++]; right--; // 向左填充 (下边界) for (int i = right; i >= left && index < N; i--) matrix[bottom][i] = nums[index++]; bottom--; // 向上填充 (左边界) for (int i = bottom; i >= top && index < N; i--) matrix[i][left] = nums[index++]; left++; } // 输出结果 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cout << matrix[i][j]; if (j < n - 1) cout << " "; } cout << endl; } return 0; } ``` #### 关键点说明 1. **矩阵尺寸计算**： - 从 $\lfloor \sqrt{N} \rfloor$ 开始递减寻找 $n$ - 确保 $n$ 是 $N$ 的因子且 $m = N/n \ge n$ - 满足 $m - n$ 最小化条件 2. **四指针填充法**： - `top/bottom` 控制垂直边界 - `left/right` 控制水平边界 - 每完成一个方向收缩对应边界 - 循环条件 `index < N` 确保填充完整 3. **边界处理**： - 每个 `for` 循环包含 `index < N` 检查 - 防止单行/单列情况下的越界访问 - 示例：$N=12$ 时矩阵尺寸 $4\times3$ #### 示例输入/输出 **输入**： ``` 12 37 76 20 98 44 53 12 90 67 24 88 61 ``` **输出**（部分）： ``` 98 90 88 24 20 76 67 53 44 61 12 37 ```