设计品牌网站,昆明市住房和城乡建设局网站,wordpress rockgroup,wordpress快速建站教程视频PAT 1035 插入与归并 题目描述思路讲解代码展示 题目描述 思路讲解
分析#xff1a;先将i指向中间序列中满足从左到右是从小到大顺序的最后一个下标#xff0c;再将j指向从i1开始#xff0c;第一个不满足a[j] b[j]的下标#xff0c;如果j顺利到达了下标n#xff0c;说明… PAT 1035 插入与归并 题目描述思路讲解代码展示 题目描述 思路讲解
分析先将i指向中间序列中满足从左到右是从小到大顺序的最后一个下标再将j指向从i1开始第一个不满足a[j] b[j]的下标如果j顺利到达了下标n说明是插入排序再下一次的序列是sort(a, ai2);否则说明是归并排序。归并排序就别考虑中间序列了直接对原来的序列进行模拟归并时候的归并过程i从0到n/k每次一段段得sort(a i * k, a (i 1) * k);最后别忘记还有最后剩余部分的sort(a n / k * k, a n);这样是一次归并的过程。直到有一次发现a的顺序和b的顺序相同则再归并一次然后退出循环
注意一开始第三个测试点一直不过天真的我以为可以模拟一遍归并的过程然后在过程中判断下一步是什么。。然而真正的归并算法它是一个递归过程。。也就是先排左边一半把左边的完全排列成正确的顺序之后再排右边一半的。。而不是左右两边一起排列的。。后来改了自己的归并部分判断的代码就过了。。。◕‿◕
代码展示
#include iostream
#include algorithmusing namespace std;int main() {int n, a[100], b[100], i, j;cin n;for (int i 0; i n; i)cin a[i];for (int i 0; i n; i)cin b[i];for (i 0; i n - 1 b[i] b[i 1]; i);for (j i 1; a[j] b[j] j n; j);if (j n) {cout Insertion Sort endl;sort(a, a i 2);} else {cout Merge Sort endl;int k 1, flag 1;while (flag) {flag 0;for (i 0; i n; i) {if (a[i] ! b[i])flag 1;}k k * 2;for (i 0; i n / k; i)sort(a i * k, a (i 1) * k);sort(a n / k * k, a n);}}for (j 0; j n; j) {if (j ! 0) printf( );printf(%d, a[j]);}return 0;
}
