nyoj322Sort归并排序
发布日期:2021-06-29 11:13:56
浏览次数:4
分类:技术文章
本文共 1962 字,大约阅读时间需要 6 分钟。
先收藏起来,改日在自己写一篇。 nyoj322Sort 时间限制:1000 ms | 内存限制:65535 KB 难度:4 描述 You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need. For example, 1 2 3 5 4, we only need one operation : swap 5 and 4. 输入 The input consists of T number of test cases.(<0T<1000) Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n. 输出 For each case, output the minimum times need to sort it in ascending order on a single line. 样例输入 2 3 1 2 3 4 4 3 2 1 样例输出 0 6
//归并排序//http://blog.csdn.net/yuehailin/article/details/68961304 #include#include using namespace std;void mergeArray(int number[], int first, int mid, int last, int temp[]);void mergeSort(int number[], int first, int last, int temp[]);int count;int main() { int t, n, number[1005], temp[1005]; scanf("%d", &t); while (t--) { count = 0; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &number[i]); mergeSort(number, 0, n-1, temp);// for (int i = 0; i < n; i++) printf("%d ", number[i]);// printf("\n"); printf("%d\n", count); } return 0;}void mergeArray(int number[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int position = 0; while (i <= mid && j <= last) { if (number[i] <= number[j]) { temp[position++] = number[i++]; }else { count += mid - i + 1; temp[position++] = number[j++]; } } while (i <= mid) temp[position++] = number[i++]; while (j <= last) temp[position++] = number[j++]; for (i = 0; i < position; i++) number[first+i] = temp[i];}void mergeSort(int number[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergeSort(number, first, mid, temp); mergeSort(number, mid+1, last, temp); mergeArray(number, first, mid, last, temp); }}
转载地址:https://blog.csdn.net/ZWHSOUL/article/details/79490993 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月30日 04时53分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
JAVA笔记(四)--三大结构语句
2019-04-29
JAVA语言基础(五)--数组
2019-04-29
JAVA项目案例详解带代码
2019-04-29
JAVA九种排序算法详解
2019-04-29
JAVA笔记(六)面向对象--类和对象
2019-04-29
JAVA笔记(十一)面向对象--多态
2019-04-29
webpack打包错误:Invalid configuration object. Webpack has been initialised using a configuration object
2019-04-29
TypeError: this.getOptions is not a function
2019-04-29
el-table 二维数组合并行
2019-04-29
js获取当月的天数
2019-04-29
多个相邻的盒子外边框合并的问题
2019-04-29
js实现复制功能
2019-04-29
UR5e机械臂运行一直阻塞在waitForServer
2019-04-29
ROS把pkg1下的某个头文件和源文件生成动态链接库供pkg2调用
2019-04-29
使用urdf_tutorial快速可视化urdf文件
2019-04-29
SQl 数据完整性(随堂博客)
2019-04-29
左连接、右连接、内连接
2019-04-29
MySQL DQL语句基础(随堂博客)
2019-04-29
MySQL基础练习
2019-04-29