2014 HDU多校弟五场A题 【归并排序求逆序对】

这题是2Y，第一次WA贡献给了没有long long 的答案QAQ

题意不难理解，解题方法不难。

先用归并排序求出原串中逆序对的个数然后拿来减去k即可，如果答案小于0，则取0

学习了归并排序求逆序对的方法，可以拿来当模板 TVT

贴代码了：

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <math.h>

 #include <iostream>

 #include <stack>

 #include <queue>

 #include <algorithm>

 #define ll long long

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int MAXN = ;

 const int N = ;

 int a[N],tmp[N];

 //int array_a[N], array_b[N];

 ll ans;

 int n, k;

 void Merge(int l,int m,int r)

 {

     int i = l;

     int j = m + ;

     int k = l;

     while(i <= m && j <= r)

     {

         if(a[i] > a[j])

         {

             tmp[k++] = a[j++];

             ans += m - i + ;

         }

         else

         {

             tmp[k++] = a[i++];

         }

     }

     while(i <= m) tmp[k++] = a[i++];

     while(j <= r) tmp[k++] = a[j++];

     for(int i=l;i<=r;i++)

         a[i] = tmp[i];

 }

 void Merge_sort(int l,int r)

 {

     if(l < r)

     {

         int m = (l + r) >> ;

         Merge_sort(l,m);

         Merge_sort(m+,r);

         Merge(l,m,r);

     }

 }

 int main()

 {

     int i, j;

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

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

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

             //array_a[i] = array_b[i] = a[i];

         }

         ans = ;

         Merge_sort(,n-);

         ans -= k;

         if(ans <=  )    printf("0\n");

         else cout << ans << endl;

     }

     return ;

 }

2014 HDU多校弟五场A题 【归并排序求逆序对】的相关教程结束。