hdu 4911 Inversion

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 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

树状数组求逆序对，如果总对数大于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_back
15 #define mmax 100000
16 #define ll __int64
17 #define mod 1000000007
18 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
",sum);
64     }
65 }