好贷网好贷款

九度OJ 1348 数组中的逆序对 -- 归并排序

发布时间:2016-12-4 7:54:38 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"九度OJ 1348 数组中的逆序对 -- 归并排序",主要涉及到九度OJ 1348 数组中的逆序对 -- 归并排序方面的内容,对于九度OJ 1348 数组中的逆序对 -- 归并排序感兴趣的同学可以参考一下。

题目地址:http://ac.jobdu.com/problem.php?pid=1348 题目描述: 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 输入: 每个测试案例包括两行: 第一行包含一个整数n,表示数组中的元素个数。其中1 <= n <= 10^5。 第二行包含n个整数,每个数组均为int类型。 输出: 对应每个测试案例,输出一个整数,表示数组中的逆序对的总数。 样例输入: 4 7 5 6 4 样例输出: 5 #include <stdio.h> long long cnt; void Merge (int data[], int start, int mid, int end){ int new_data[100000]; int i = start; int j = mid + 1; int k = start; while (i <= mid && j <= end){ if (data[i] > data[j]){ new_data[k] = data[i]; ++i; ++k; cnt += (end - j + 1); } else{ new_data[k] = data[j]; ++j; ++k; } } while (i <= mid){ new_data[k] = data[i]; ++i; ++k; } while (j <= end){ new_data[k] = data[j]; ++j; ++k; } while (start <= end){ data[start] = new_data[start]; ++start; } } void MergeSort (int data[], int start, int end){ int mid; if (start < end){ mid = (start + end) >> 1; MergeSort (data, start, mid); MergeSort (data, mid + 1, end); Merge (data, start, mid, end); } } int main(void){ int n; int data[100000]; int i; while (scanf ("%d", &n) != EOF){ for (i=0; i<n; ++i) scanf ("%d", &data[i]); cnt = 0; MergeSort (data, 0, n - 1); printf ("%lld\n", cnt); } return 0; } 清橙OJ上相似的题目:http://oj.tsinsen.com/A1078

上一篇:关于SQL Server 2012/2008 Management Studio 与迅雷冲突的解决方法
下一篇:Hash表的一种实现

相关文章

相关评论