【a703】求逆序对
逆序
2023-09-14 09:03:46 时间
Time Limit: 10 second
Memory Limit: 2 MB
问题描述
给定一个序列a1,a2...an。如果存在i小于j 并且ai大于aj,那么我们称之为逆序对,求给定序列中逆序对的数目
Input
第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。
Output
所有逆序对的总数
Sample Input
4 3 2 3 2
Sample Output
3
【题解】
在进行归并排序的同时求逆序对。
我们在进行归并排序时。
分成l..mid和mid+1..r
假设左边循环变量为i,右边的循环变量为j。
则当我们找到一个i和j满足a[i] > a[j]时。
因为左边,右边都是有序的,则a[i+1..mid]都大于a[j];
而之后我们会吧a[j]加入到temp数组中,此后a[j]不再出现。
则逆序对的数目增加mid-i+1;
然后逆序对数目用数据范围大的类型存储就好了。
【代码】
#include <cstdio> int n,a[100009],temp[100009]; double tot = 0; void input_data() { scanf("%d",&n); for (int i = 1;i <= n;i++) scanf("%d",&a[i]); } void mergesort(int l,int r) //对区间[l,r]进行分割 { if (l == r) return; //只剩一个元素则认为其是有序的。 int mid = (l+r)/2; //获取中间的位置 mergesort(l,mid);mergesort(mid+1,r); //将这个位置的左边和右边进行不断切割。 int i = l,j = mid+1,k = l; while (i <= mid && j <= r) //开始进行二路归并。 if (a[i] <= a[j]) //比较小的数放到temp数组中去 temp[k++] = a[i++]; else //在排序的同时顺便求逆序对 { tot+=mid-i+1; temp[k++] = a[j++]; } while (i <= mid) temp[k++] = a[i++]; while (j <= r) //剩下相同的数字也要放进temp数组 temp[k++] = a[j++]; for (int w = l;w<=r;w++) //最后再把temp数组赋值给原数组 a[w] = temp[w]; } void output_ans() { printf("%.0lf",tot); } int main() { //freopen("F:\\rush.txt","r",stdin); input_data(); mergesort(1,n); output_ans(); return 0; }
相关文章
- java实现求逆序对
- java实现求逆序对
- Python实现按照指定要求逆序输出一个数字的方法
- 788. 逆序对的数量
- 程序员的算法趣题Q42: 将牌洗为逆序
- ZZNUOJ_C语言1114:逆序(完整代码)
- ZZNUOJ_用C语言编写程序实现1159:逆序输出数组元素(指针专题)(附完整源码)
- 习题 3.12 给出一个不多于5位的正整数,要求:1. 求出它是几位数;2. 分别打印出每一位数字;3. 按逆序打印出各位数字,例如原数位321,应输出123。
- 习题 6.14 将n个数按输入时顺序的逆序排列,用函数实现。
- 例6.1 对10个数组元素依次赋值为0,1,2,3,4,5,6,7,8,9,要求按逆序输出。
- NC118 数组中的逆序对
- POJ2828 Buy Tickets 【线段树】+【单点更新】+【逆序】
- 求逆序对