Inversion

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

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

1 2

题意：n个数。最多有k次相邻位置的数的交换，问最小的逆序数为多少

思路：保证每次交换逆序数都减小，能够參考冒泡排序的做法。最后仅仅要计算原数列逆序数，然后减掉k就可以。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             using namespace std;const int maxn = 100000+10;int sum[maxn];int n,k;int num[maxn],tn[maxn];map
              
                mma;bool cmp(int a,int b){ return a > b;}int lowbit(int x){ return x&(-x);}void add(int x,int d){ while(x < maxn){ sum[x] += d; x += lowbit(x); }}int getS(int x){ int ret = 0; while(x > 0){ ret += sum[x]; x -= lowbit(x); } return ret;}int main(){ while(~scanf("%d%d",&n,&k)){ mma.clear(); memset(sum,0,sizeof sum); for(int i = 1; i <= n; i++){ scanf("%d",&num[i]); tn[i] = num[i]; } sort(tn+1,tn+n+1,cmp); int i = 1,cnt = 1; while(i <= n){ mma[tn[i]] = cnt; int j = i+1; while(j <= n && tn[i]==tn[j]){ j++; } cnt++; i = j; } long long ret = 0; for(int i = 1; i <= n; i++){ ret += getS(mma[num[i]]-1); add(mma[num[i]],1); } long long ans = ret-k; if(ans < 0) ans = 0; cout<
               
                <