当前位置： 移动技术网 > IT编程>开发语言>C/C++ > ACM--归并排序&&树状数组--nyoj 117--求逆序数

ACM--归并排序&&树状数组--nyoj 117--求逆序数

2018年11月05日  | 移动技术网IT编程  | 我要评论

优游幻世,追梦3dna,不知火舞漫画全集

南阳oj题目地址：

时间限制：2000ms | 内存限制：65535kb 难度：5

描述

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

现在，给你一个n个元素的序列，请你判断出它的逆序数是多少。

比如 1 3 2 的逆序数就是1。

输入
第一行输入一个整数t表示测试数据的组数（1<=t<=5)
每组测试数据的每一行是一个整数n表示数列中共有n个元素（2〈=n〈=1000000）
随后的一行共有n个整数ai(0<=ai<1000000000)，表示数列中的所有元素。

数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。
输出
输出该数列的逆序数
样例输入
2
2
1 1
3
1 3 2
样例输出
0
1
 

 

求逆序数：用归并排序来做，效率还是很高的；

归并排序利用分治的思想，先把一个数组分成一个个序列，然后对一个个序列排序，把排好序的序列，在合并到原来的数组中。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000001;
int a[maxn],b[maxn];
long long sum;
/**
  归并
*/
void merge(int begin,int mid,int end){
    int i=begin,j=mid+1,pos=begin;
    //对一个个序列排序的过程
    while(i<=mid && j<=end){
        if(a[i]<=a[j]){
            b[pos++]=a[i++];
        }else{
            b[pos++]=a[j++];
            sum+=mid-i+1;//求逆序数
        }
    }
    while(i<=mid) b[pos++]=a[i++];
    while(j<=end) b[pos++]=a[j++];
    for(int i=begin,j=begin;i<=end;i++,j++)
        a[i]=b[j];
}
/**
  排序
*/
void sort(int begin,int end){
    if(begin<end){ int="" mid="(begin+end)/2;" sum="0;" i="1;i<=n;i++)" return="" pre="">



</end){></algorithm></cstring></cstdio>

 

 

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网