HDU 4911 Inversion（归并排序求逆序对）

Problem Description bobo has a sequence a ₁,a ₂,…,a _n. He is allowed to swap two  adjacent numbers for no more than k times. Find the minimum number of inversions after his swaps. Note: The number of inversions is the number of pair (i,j) where 1≤i<j≤n and a _i>a _j.   Input The input consists of several tests. For each tests: The first line contains 2 integers n,k (1≤n≤10 ⁵,0≤k≤10 ⁹). The second line contains n integers a ₁,a ₂,…,a _n (0≤a _i≤10 ⁹).   Output For each tests: A single integer denotes the minimum number of inversions.   Sample Input 3 1 2 2 1 3 0 2 2 1   Sample Output 1 2   Author Xiaoxu Guo (ftiasch)   Source 2014 Multi-University Training Contest 5

 【题解】

  水题，不过题意比较模糊，给一个序列，每次可以交换相邻的逆序数（i<j&&a[i]?a[j]），

 并且最多交换k次，问交换完的最小逆序对个数。

 思考一下，每次只交换相邻两个，所以也就是说每次只会减少一个逆序对，所以就是把最初的逆序数对求出来减去k即为答案。

 注意要用  long long

 【AC代码】

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int N=1e5+5; int n,node[N],m[N],str[N]; __int64 ss,mins; void Mergee(int first,int mid,int end,int a[]) { int i=first; int j=mid+1; int k=first; while(i<=mid && j<=end) { if(a[i]>a[j]) { m[k++]=a[j++]; ss += mid - i+1 ; } else { m[k++]=a[i++]; } } while(i<=mid) { m[k++]=a[i++]; } while(j<=end) { m[k++]=a[j++]; } for(int i=first;i<=end;i++) a[i]=m[i]; } void MergeSort(int first,int end,int a[]) { if(first<end) { int mid = (first+end)>>1; MergeSort(first,mid,a); MergeSort(mid+1,end,a); Mergee(first,mid,end,a); } } int main() { int k; while(~scanf("%d%d",&n,&k)) { for(int i=1;i<=n;i++) { scanf("%d",&node[i]); } ss=0; MergeSort(1,n,node); mins=ss; printf("%I64d\n",max(mins-k,(__int64)0)); } return 0; }