HDU 4911 Inversion（求逆序对）

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

题解：

题意：

给你n个数，允许相邻的交换k次，问你能得到的最小逆序对数

思路：

一开始想用树状数组来求逆序对。。后来发现1e9就放弃了。。老老实实归并排序吧，max(逆序对数减去交换次数,0)就是答案，注意要long long

代码：

#include<iostream> #include<cstring> #include<stdio.h> #include<math.h> #include<string> #include<stdio.h> #include<queue> #include<stack> #include<map> #include<vector> #include<deque> #include<algorithm> using namespace std; #define INF 100861111 #define ll long long #define eps 1e-15 int a[100005]; int t[100005]; ll ans; void Merge(int l,int r,int mid) { int i=l,j=mid+1,k=l; while(i<=mid&&j<=r) { if(a[i]>a[j]) { ans+=(mid+1-i); t[k]=a[j]; j++; } else { t[k]=a[i]; i++; } k++; } while(i<=mid) { t[k]=a[i]; i++; k++; } while(j<=r) { t[k]=a[j]; k++; j++; } for(i=l;i<=r;i++) a[i]=t[i]; } void guibin(int l,int r) { if(l<r) { int mid=(l+r)/2; guibin(l,mid); guibin(mid+1,r); Merge(l,r,mid); } } int main() { int i,j,n,x; ll k; while(scanf("%d%lld",&n,&k)!=EOF) { ans=0; for(i=0;i<n;i++) { scanf("%d",&a[i]); } guibin(0,n-1); ans=max(ans-k,(ll)0); printf("%lld\n",ans); } return 0; }