沧县网站建设公司,网站中加入百度地图,外链提交网站,wordpress文章页图片本题要求将给定的 N 个正整数按非递增的顺序#xff0c;填入“螺旋矩阵”。所谓“螺旋矩阵”#xff0c;是指从左上角第 1 个格子开始#xff0c;按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列#xff0c;满足条件#xff1a;mn 等于 N#xff1b;m≥n#xff1b;且…本题要求将给定的 N 个正整数按非递增的顺序填入“螺旋矩阵”。所谓“螺旋矩阵”是指从左上角第 1 个格子开始按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列满足条件m×n 等于 Nm≥n且 m−n 取所有可能值中的最小值。
输入格式
输入在第 1 行中给出一个正整数 N第 2 行给出 N 个待填充的正整数。所有数字不超过 104相邻数字以空格分隔。
输出格式
输出螺旋矩阵。每行 n 个数字共 m 行。相邻数字以 1 个空格分隔行末不得有多余空格。
输入样例
12
37 76 20 98 76 42 53 95 60 81 58 93输出样例
98 95 93
42 37 81
53 20 76
58 60 76 问题总结
1.没什么特别的就是一个找规律的题和机器人的那一道题有些类似机器人控制。但是需要解决几个问题。
2.寻找 m * n N 的两个数且有 mn min(m-n) 比较笨的方法。
void get_m_n(int N, int m,int n)
{int min N ;for(int i 1; i N; i){for (int j i; j N; j){if(i*j N){if(min (j-i)){min (j-i);m j;n i;}}if(i*j N){break;}}}
} 3.简单的选择排序
void sort(int *nums,int size)
{int t;for(int i0;isize;i){for(int j i1; jsize; j){if(nums[i]nums[j]){t nums[i];nums[i] nums[j];nums[j] t;}}}
}
4.数据范围m和n的取值决定了程序能不能通过测试点因此二维数组不能开太大当然可以用一维数组来优化。开辟 m * n N的一维数组将二维矩阵按行顺序存储通过计算还原元素在二维数组位置的下标即一维元素 index i * n ji和j代表二维中的下标n代表列col数量。
优化前的内存
优化后的内存 5.总体实现未优化
#include iostream
#includecstring
using namespace std;
void get_m_n(int N, int m,int n)
{int min N ;for(int i 1; i N; i){for (int j i; j N; j){if(i*j N){if(min (j-i)){min (j-i);m j;n i;}}if(i*j N){break;}}}
}
void sort(int *nums,int size)
{int t;for(int i0;isize;i){for(int j i1; jsize; j){if(nums[i]nums[j]){t nums[i];nums[i] nums[j];nums[j] t;}}}
}
int main(int argc, char const *argv[])
{bool r true,d false,l false,ufalse;int N;cinN;int *nums new int[N];memset(nums, 0, sizeof(int)*N);for(int i 0; i N; i){cinnums[i];}sort(nums,N);int m0,n0;get_m_n(N,m,n);int ans[10000][100] {0};int i0,j-1;int heng n,shu m -1;for(int index 0; index N; ){if(r){for(int step 0; step heng; step){ans[i][j] nums[index];r false;l false;u false;d true;}heng--;}if(d){for(int step0; step shu;step){ans[i][j] nums[index];d false;u false;r false;l true;}shu--;}if(l){for(int step 0; step heng; step){ans[i][--j] nums[index];l false;r false;d false;u true;}heng--;}if(u){for(int step0; step shu; step){ans[--i][j] nums[index];u false;l false;d false;r true;}shu--;}}for(int row 0; row m; row){for (int col 0; col n; col){if(coln-1){coutans[row][col] ;}else{coutans[row][col];}}coutendl;}return 0;
}6.优化方案
#include iostream
#includecstring
using namespace std;
void get_m_n(int N, int m,int n)
{int min N ;for(int i 1; i N; i){for (int j i; j N; j){if(i*j N){if(min (j-i)){min (j-i);m j;n i;}}if(i*j N){break;}}}
}
void sort(int *nums,int size)
{int t;for(int i0;isize;i){for(int j i1; jsize; j){if(nums[i]nums[j]){t nums[i];nums[i] nums[j];nums[j] t;}}}
}
int convert_i_j(int i, int j, int n)
{return i*nj;
}
int main(int argc, char const *argv[])
{bool r true,d false,l false,ufalse;int N;cinN;int *nums new int[N];memset(nums, 0, sizeof(int)*N);for(int i 0; i N; i){cinnums[i];}sort(nums,N);int m0,n0;get_m_n(N,m,n);int *answer new int[m*n];int i0,j-1;int heng n,shu m -1;for(int index 0; index N; ){if(r){for(int step 0; step heng; step){j;int value nums[index];int index_m_n convert_i_j(i,j,n);answer[index_m_n] value;r false;l false;u false;d true;}heng--;}if(d){for(int step0; step shu;step){i;int value nums[index];int index_m_n convert_i_j(i,j,n);answer[index_m_n] value;d false;u false;r false;l true;}shu--;}if(l){for(int step 0; step heng; step){j--;int value nums[index];int index_m_n convert_i_j(i,j,n);answer[index_m_n] value;l false;r false;d false;u true;}heng--;}if(u){for(int step0; step shu; step){i--;int value nums[index];int index_m_n convert_i_j(i,j,n);answer[index_m_n] value;u false;l false;d false;r true;}shu--;}}for(int row 0; row m; row){for (int col 0; col n; col){if(coln-1){coutanswer[row*ncol] ;}else{coutanswer[row*ncol];}}coutendl;}return 0;
}
