首页 > 代码库 > hdu 4911 Inversion

hdu 4911 Inversion

2024-07-15 23:20:51   212人阅读

Inversion

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 68    Accepted Submission(s): 23


Problem Description
bobo has a sequence a1,a2,…,an. 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 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 1
2 2 1
3 0
2 2 1
 
Sample Output
1
2
树状数组求逆序对，如果总对数大于k 就减k，否则置为0
 1 #include<iostream> 2 #include<string> 3 #include<cstdio> 4 #include<vector> 5 #include<queue> 6 #include<stack> 7 #include<algorithm> 8 #include<cstring> 9 #include<stdlib.h>10 #include<string>11 #include<cmath>12 #include<map>13 using namespace std;14 #define pb push_back15 #define mmax 10000016 #define ll __int6417 #define mod 100000000718 ll p[101000];19 int ac[101000],tmp[101000],cnt;20 int n,m;21 int Find(int x){22     int l=1,r=cnt,mid,tt=10000000;23     while(l<=r){24         mid=(l+r)>>1;25         if(tmp[mid]>=x) tt=min(tt,mid),r=mid-1;26         else l=mid+1;27     }28     return tt;29 }30 void update(int pos,int num){31     while(pos>0){32         p[pos]+=num;33         pos-=pos&(-pos);34     }35 }36 ll getnum(int pos){37     ll sum=0;38     while(pos<=cnt){39         sum+=p[pos];40         pos+=pos&(-pos);41     }42     return sum;43 }44 int main(){45     while(cin>>n>>m){46         for(int i=1;i<=n;i++){47              scanf("%d",&ac[i]);48              tmp[i]=ac[i];49         }50         memset(p,0,sizeof(p));51         sort(tmp+1,tmp+1+n);离散化52         cnt=0;53         tmp[++cnt]=tmp[1];54         ll sum=0;55         for(int i=2;i<=n;i++) if(tmp[i]!=tmp[cnt]) tmp[++cnt]=tmp[i];56         for(int i=1;i<=n;i++){57             int x=Find(ac[i]);58             sum+=getnum(x+1);59             update(x,1);60         }61         if(sum>=m) sum-=m;62         else sum=0;63         printf("%I64d\n",sum);64     }65 }

 


联系
我们