7-1求逆序对数目

目录

题目描述

输入样例:

输出样例:

逆序对的含义：

具体思路：

归并排序：

求逆序对：

代码实现：

对于mid-z+1举个例子 

---

题目描述

注意：本问题算法的时间复杂度要求为O(nlogn), 否则得分无效

题目来源：http://poj.org/problem?id=1804
Background
Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task.

Problem
Here's what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:
Start with: 2 8 0 3
swap (2 8) 8 2 0 3
swap (2 0) 8 0 2 3
swap (2 3) 8 0 3 2
swap (8 0) 0 8 3 2
swap (8 3) 0 3 8 2
swap (8 2) 0 3 2 8
swap (3 2) 0 2 3 8
swap (3 8) 0 2 8 3
swap (8 3) 0 2 3 8

So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps:
Start with: 2 8 0 3
swap (8 0) 2 0 8 3
swap (2 0) 0 2 8 3
swap (8 3) 0 2 3 8

The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond's mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question in O(nlogn). Rest assured he will pay a very good prize for it.

输入格式:

The first line contains the length N (1 <= N <= 1000) of the sequence；
The second line contains the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.

输出格式:

Print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence.

输入样例:

在这里给出一组输入。例如：

6
-42 23 6 28 -100 65537

输出样例:

在这里给出相应的输出。例如：

5

如标题所示，题目简单来说就是求一个数组中逆序对的个数 

逆序对的含义：

对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对

另外一个元素可能存在于多个逆序对中，例如：

第i个元素，第j个元素，第k个元素存在，i<j<k且a[i]>a[j]>a[k]则有两个逆序对，且都含有a[i]

以题目为例

-42 23 6 28 -100 65537

从小到大排序为

-100 -42 6 23  28 65537

-100比它左边的-42 23 6 28都小，所以逆序对加4

-100与-42为一个逆序对

-100与23为一个逆序对

-100与6为一个逆序对

-100与28为一个逆序对

6比它左边的23小，所以逆序对加1

6与23为一个逆序对

4+1=5即为答案

具体思路：

归并排序：

1、将序列平均分为两个区间（部分）

2、递归排序左区间和右区间

3、将左右两个区间已经排序好的序列合并成一个有序的序列

求逆序对：

分为三种情况

假设需要对比的两个元素

1、两个元素都在区间的左边

2、两个元素都在区间的右边

3、两个元素一个在区间左边一个在区间右边

代码实现：

#include<iostream>
using namespace std;
#define int long long
const int N=1e5+7;
int sz[N];//存储序列
int ans=0;
void gb_px(int l,int r)
{if(l>=r)return;//如果左边的下标大于等于右边，代表已经无法分成两部分了，所以返回即可int mid=(l+r)>>1;//相当于mid=(l+r)/2;gb_px(l,mid);//进入左区间排序gb_px(mid+1,r);//进入右区间排序int z=l,y=mid+1,xb=0;int zs[r-l+1];//可以用全局变量，但是数组长度肯定不超过r-l+1while(z<=mid&&y<=r)//左边的起始点不能超过中点，右边的起始点不能超过右边的右边的界限{if(sz[z]<=sz[y])//如果左边的数小于等于右边，则将左边的元素放在前面，用zs数组暂时存，此时左边的下标往右移动一位{zs[xb++]=sz[z++];}else//否则如果右边的数小于左边，则将右边的元素放在前面，用zs数组暂时存，此时右边的下标往右移动一位{zs[xb++]=sz[y++];ans+=mid-z+1;//关键一步，此时中点减去左边指针的下标加一即为对于sz[y]这个数，实际计算的是在左区间中大于右区间指向的这个数的个数，在这个区间中的逆序对的个数。}}//移动完以后还会有剩下的数，显然他们已经是有序的了while(z<=mid)//左半边还剩下几个元素，全都加进去{zs[xb++]=sz[z++];}while(y<=r)//右半边还剩下几个元素，全都加进去{zs[xb++]=sz[y++];}for(int i=l,j=0;i<=r;i++,j++)//更新l到r的数组元素的顺序，因为zs数组是从0开始为下标存储的{sz[i]=zs[j];}
}
signed main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>sz[i];}gb_px(0,n-1);//进入归并排序，数组下标为0到n-1cout<<ans;
}

对于mid-z+1举个例子 

例如

现在存在一个区间，他们的开始下标假设为0，此时的mid为（0+7）/2=3，即z=0，mid=3，y=4。

1 2 3 4 2 3 4 5

很明显

可以分成

1 2 3 4为左区间

2 3 4 5为右区间

左区间为上一轮排序好的

右区间也为上一轮排序好的

左区间中1 2小于右区间的2所以将

1 2放入zs数组中存储

此时左区间的3显然大于右区间的2，所以此时逆序对的个数为3-2+1=2个

为什么是mid-z+1呢，因为，左区间右区间序列是已经排序好的

可以发现3后面的所有元素都是大于右区间中2的，即算出了左区间中大于当前右区间指向的这个数2的元素的个数，为2个