精灵魔法【归并排序】

今天放假了，寻思着在洛谷上把任务计划里的题都弄清楚，但无意间看了一眼老姚博客，直接多了四道题，还是先看看考试题吧（又是上不去题库的一天）

题目描述

族领地尚未受到冥界恶灵的侵入。族长Galanodel 为了帮助米德加尔特抵御外敌，对邪恶亡灵军团使用了高等魔法，从而使得亡灵军团每个士兵的行进速度变得不一致，从而打乱冥王 Hel安排的最佳阵型。
由于这个军团离 Midgard 还很远，因此在抵达 Midgard 之前，对于A,B 两个亡灵，若 A 的初始位置在 B 后面且 A 的速度比 B 快,A 就会冲到 B 的前面去。现在 Galanodel想知道，会有多少对亡灵之间出现反超现象？

Input

第一行一个整数 n，表示排成一队的邪恶亡灵军团有多少人。
第二行 n 个整数 a[i]，表示邪恶亡灵们在数轴上的初始坐标。数据保证这些坐标全部不同。亡灵军团向数轴正方向前进。
第三行 n 个整数 v[i]，表示邪恶亡灵们的行进速度。

Output

一行一个正整数 k，表示「反超」的个数。

Sample Input

3
1 2 3
2 1 3

Sample Output

Hint

对于 30% 的数据，1<=N<=1000；
对于100% 的数据，1<=N<=10^5。
所有数据的绝对值均不超过 maxlongint。
来源：cogs1144

思路分析

又是废话超多的一道题~~（不是）~~

一句话题意：给了先后位置，给了各自速度，求反超数。

一眼看上去就想跑暴力，两重循环枚举，效率O(n^2)，但是不用提交也知道会爆，不然就太太太太水了

难点：求逆序对个数，排序前的数组和排序后的数组需要保持联系，要是sort大法，那排序完以后就没它什么事情了
- 补充一下逆序对的定义：对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。
Key：用到了一个思路很巧妙的排序方法——归并排序
关于归并排序：

去借鉴（扒）了一下老姚以前的博客
- 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
- 过程：
  1. 把长度为n的输入序列分成两个长度为n/2的子序列；
  2. 对这两个子序列分别采用归并排序；
  3. 将两个排序好的子序列合并成一个最终的排序序列
- 总结：递归处理，分成两部分，排好了再分别从前往后组成完整的序列。即先分排，再合并
  
  再扒张图

代码

不要问我是不是扒的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int maxn=1e5+5,Inf=0x3f3f3f;
struct Node{
    LL pos,v;
    bool operator <(const Node &a)const{
        return pos<a.pos;
    }
}e[maxn];
LL a[maxn],b[maxn],ans=0; //b作为临时数组存储数据
int n; 
void Merge(int l,int mid,int r){//合并操作
    int i=l,j=mid+1,k=0;//i指向前面区间第一个元素，j指向后面区间第一元素
    while(i<=mid && j<=r){//取两个序列前面的较小者
        if(a[i]<=a[j])b[++k]=a[i++];
        else{
            ans+=mid-i+1;//a[i]~a[mid]均能和a[j]组成逆序对
            b[++k]=a[j++];
        } 
    }//跳出循环两个序列中有一个为空
    while(i<=mid)//若比较完之后，第一个有序区仍有剩余
        b[++k]=a[i++];
    while(j<=r)//若比较完之后，第二个有序区仍有剩余
        b[++k]=a[j++];
    for(i=l,k=1;i<=r;++i,++k)//把合并后的排好序的序列拷贝到数组a[l,r]
        a[i]=b[k];
}
void Merge_sort(int l,int r){
    if(l<r){//把区间分成两部分
        int mid=l+(r-l)/2;
        Merge_sort(l,mid);//递归左区间
        Merge_sort(mid+1,r);//递归右区间
        Merge(l,mid,r);//合并左右两区间
    }
}
int main(){
    n = read();
    for(int i=1;i<=n;++i)scanf("%lld",&e[i].pos);
    for(int i=1;i<=n;++i)scanf("%lld",&e[i].v);
    sort(e+1,e+n+1);
    for(int i=1;i<=n;++i)a[i]=e[i].v;
    Merge_sort(1,n);
    printf("%lld
",ans);
}

发量成功减0.5%

顺便吼一句：高考加油，衡中必胜！