Inversion

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

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

Author

Xiaoxu Guo (ftiasch)

Source

题解及代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;__int64 ans=0;void merge(int Array[],int l,int m,int r){    int temp[100110];    int i=l,j=m+1,k=0;    while(i<=m&&j<=r)    {        if(Array[i]<=Array[j])        {            temp[k++]=Array[i];            i++;        }        else        {            temp[k++]=Array[j];            j++;            ans+=(m-i+1);     //求逆序数的关键        }    }    while(i<=m) {temp[k++]=Array[i];i++;}    while(j<=r) {temp[k++]=Array[j];j++;}    for(i=l,j=0;i<=r&&j
        
         =r) return;    int m=(l+r)/2;    mergesort(Array,l,m);    mergesort(Array,m+1,r);    merge(Array,l,m,r);}int main(){    int n,k;    int Array[100110];    while(scanf("%d%d",&n,&k)!=EOF)    {        ans=0;        for(int i=0;i
         
          >Array[i];        }        mergesort(Array,0,n-1);        if(k>=ans)        {            printf("0\n");        }        else printf("%I64d\n",ans-k);    }    return 0;}/*简单题，本题主要是求出当前数列的逆序数。我们直到每次调序都能将逆序数降低1。我们先求出逆序数。然后推断，当给出的调序次数小于当前序列的逆序数时，输出ans-k，否则输出0。