点我看题
题意:给一个长度为n的序列,问经过最多k次两两交换(仅限相邻的数之间),最少还有多少逆序对.
分析:归并求出总的逆序对数,然后ans=max(求出的总逆序对-k,0).
哇&#$%,Anything is possible.
参考代码:
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long LL; const int maxn = 1e5+10; int n; LL k; int a[maxn]; int tmp[maxn]; LL ans;//emmmmmm数据有点大 用LL才能过 void Merge( int l, int mid, int r) { int i = l; int j = mid+1; int k = l; while( i <= mid && j <= r) { if( a[i] > a[j]) { tmp[k++] = a[j++]; ans += mid-i+1; } else tmp[k++] = a[i++]; } while( i <= mid) tmp[k++] = a[i++]; while( j <= r) tmp[k++] = a[j++]; for( int i = l; i <= r; i++) a[i] = tmp[i]; } void MergeSort( int l, int r) { if( l < r) { int mid = (l+r)>>1; MergeSort(l,mid); MergeSort(mid+1,r); Merge(l,mid,r); } } int main() { while( ~scanf("%d%lld",&n,&k)) { for( int i = 0; i < n; i++) scanf("%d",&a[i]); ans = 0; MergeSort(0,n-1); printf("%lld\n",max(0LL,ans-k)); } return 0; }