HDU 3743 Frosh Week(归并排序求逆序对)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3743

题目意思就是给你一个长为n的序列,让你求逆序对.我用的是归并排序来求的.归并排序有一个合并的过程,分前后两段,当a[i] > a[j]时,说明a[j]比前面那段啊[i],a[i+1],a[i+2]....,a[mid],比这些都要小,所以总逆序对数要加上mid-i+1.

 // File Name: HDU3743.cpp

 // Author: xiaxiaosheng

 // Created Time: 2015年03月09日 星期一 21时54分45秒

 #include<vector>

 #include<list>

 #include<map>

 #include<set>

 #include<deque>

 #include<stack>

 #include<bitset>

 #include<algorithm>

 #include<functional>

 #include<numeric>

 #include<utility>

 #include<sstream>

 #include<iostream>

 #include<iomanip>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #include<ctime>

 using namespace std;

 typedef __int64 INT;

 const int maxn = 10e6+;

 int n,A[maxn],temp[maxn];

 INT ans;

 void merger(int *A,int s,int mid,int e)

 {

     int k = ,i = s,j = mid+;

     while(i <= mid && j <= e)

     {

         if(A[i] < A[j])

             temp[k++] = A[i++];

         else

         {

             ans += (mid-i+);

             temp[k++] = A[j++];

         }

     }

     while(i <= mid) temp[k++] = A[i++];

     while(j <= e) temp[k++] = A[j++];

     for(int i = ;i < k;++i)

         A[s+i] = temp[i];

 }

 void mergersort(int *A,int s,int e)

 {

     if(s < e)

     {

         int mid = (s + e) / ;

         mergersort(A,s,mid);

         mergersort(A,mid+,e);

         merger(A,s,mid,e);

     }

 }

 int main(){

     while(scanf("%d",&n)!=EOF)

     {

         for(int i = ;i < n;++i)

             scanf("%d",&A[i]);

         ans = ;

         mergersort(A,,n-);

         printf("%I64d\n",ans);

     }

     return ;

 }

HDU 3743 Frosh Week(归并排序求逆序对)的相关教程结束。