henrytb 的博客

henrytb 的博客

题解 P1774 【最接近神的人_NOI导刊2010提高(02)】

posted on 2018-12-23 15:19:01 | under 题解 |

看了一眼题面...

裸的逆序对...

归并...

注意开long long就可以了...

附代码:

//直接复制不能过哦
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define Mid ((L+R)/2)
using namespace std;
const int N=1000005;
long long A[N],B[N],count=0,n;
void work(int L,int R){
    if(L==R)return;
   work(L,Mid);
   work(Mid+1,R);
    int tl=L,tr=Mid+1,t=L;
    while(tl<=Mid&&tr<=R){
        if(A[tl]<=A[tr])B[t++]=A[tl++];
       else B[t++]=A[tr++],count+=tr-t;
    }
    while(tl<=Mid) B[t++]=A[tl++];
    while(tr<=R) B[t++]=A[tr++];
   for(int i=L;i<=R;i++)A[i]=B[i];
}
int main(){
    scanf("%lld",&n); 
   for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
    work(1,n);
    printf("%lld",count);
    return 0;
}
//优秀的归并