InversionTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 2003Accepted Submission(s): 787
Problem Description
bobo has a sequence a1,a2,…,an. He is allowed to swap twoadjacentnumbers 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 ai>aj.
Input
The input consists of several tests. For each tests:The first line contains 2 integers n,k (1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an(0≤ai≤109).
Output
For each tests:A single integer denotes the minimum number of inversions.
Sample Input
3 12 2 13 02 2 1
Sample Output
12
Author
Xiaoxu Guo (ftiasch)
Source
Recommend
We have carefully selected several similar problems for you:51975196519351925189
题意：求n个数的逆序对数，可以交换k次相邻的，所以求出原序列的逆序对后减去k即可。
思路：求逆序对有两种方法，归并排序和树状数组。逆序对的几种求法
代码：
//树状数组#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 100005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;int n,k,len;int bit[maxn];int a[maxn],num[maxn];map<int,int>pos;int cmp(int a,int b){return a>b;}int Lowbit(int i){return i&-i;}ll sum(int i){ll s=0;while (i>0){s+=bit[i];i-=Lowbit(i);}return s;}void add(int i,int x){while (i<maxn){bit[i]+=x;i+=Lowbit(i);}}ll solve(){int i,j;ll ans=0;FRE(i,1,n){ans+=sum(pos[num[i]]-1);add(pos[num[i]],1);}ans-=k;if (ans<0) ans=0;return ans;}int main(){int i,j;while (~sff(n,k)){pos.clear();mem(bit,0);FRE(i,1,n){sf(a[i]);num[i]=a[i];}sort(a+1,a+n+1,cmp);len=1;pos[a[1]]=len;FRE(i,2,n) //map去重，离散化if (a[i]!=a[i-1])pos[a[i]]=++len;pf("len=%d\n",len);pf("%I64d\n",solve());}return 0;}//归并排序#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 100005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;int a[maxn];int n,k;__int64 ans;void Merge(int a[],int l,int mid,int r){int i,j,k=l;int *b=new int[r+1];FRE(i,l,r) b[i]=a[i];i=l,j=mid+1;while (i<=mid&&j<=r){if (b[i]<=b[j])a[k++]=b[i++];else{a[k++]=b[j++];ans+=(mid-i+1);}}while (i<=mid) a[k++]=b[i++];while (j<=r) a[k++]=b[j++];delete []b;}void Merge_sort(int a[],int l,int r){if (l==r) return ;int mid=(l+r)>>1;Merge_sort(a,l,mid);Merge_sort(a,mid+1,r);Merge(a,l,mid,r);}int main(){int i,j;while (~sff(n,k)){FRE(i,1,n)sf(a[i]);ans=0;Merge_sort(a,1,n);ans-=k;if (ans<0) ans=0;pf("%I64d\n",ans);}return 0;}
，始终调整好自己观风景的心态，
