首页 > 代码库 > 2014 HDU多校弟五场A题 【归并排序求逆序对】

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

2024-07-15 23:20:08   221人阅读

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

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

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

 

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

贴代码了：

 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <iostream> 6 #include <stack> 7 #include <queue> 8 #include <algorithm> 9 10 #define ll long long11 using namespace std;12 const int INF = 0x3f3f3f3f;13 const int MAXN = 1111;14 const int N = 100005;15 16 int a[N],tmp[N];17 //int array_a[N], array_b[N];18 ll ans;19 int n, k;20 21 void Merge(int l,int m,int r)22 {23     int i = l;24     int j = m + 1;25     int k = l;26     while(i <= m && j <= r)27     {28         if(a[i] > a[j])29         {30             tmp[k++] = a[j++];31             ans += m - i + 1;32         }33         else34         {35             tmp[k++] = a[i++];36         }37     }38     while(i <= m) tmp[k++] = a[i++];39     while(j <= r) tmp[k++] = a[j++];40     for(int i=l;i<=r;i++)41         a[i] = tmp[i];42 }43 44 void Merge_sort(int l,int r)45 {46     if(l < r)47     {48         int m = (l + r) >> 1;49         Merge_sort(l,m);50         Merge_sort(m+1,r);51         Merge(l,m,r);52     }53 }54 55 int main()56 {57     int i, j;58     while(EOF != scanf("%d%d",&n,&k)){59         for(i=0;i<n;i++){60             scanf("%d",&a[i]);61             //array_a[i] = array_b[i] = a[i];62         }63         ans = 0;64         Merge_sort(0,n-1);65         ans -= k;66         if(ans <= 0 )    printf("0\n");67         else cout << ans << endl;68     }69     return 0;70 }

 


联系
我们