HDU_4911_Inversion_归并统计逆序对_杭电多校A题

Inversion

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 5865    Accepted Submission(s): 2014

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

 

 

1.题意：

一个包含n个数的数列，你可以操作不超过k次，每次可以交换相邻的两个数。问你最后逆序对数目的最小值。

2.题解：

（1）每次交换操作，只能减少一个逆序对，例如 （a>b）（b>c）（c>d）有a,b,c,d这个数列，通过交换（b,c）得到a,c,b,d，那么只是（b,c）这对逆序对消失了，其他的逆序关系不受影响。

（2）如果原数列含有sum个逆序对，那么你通过交换可以得到Max(sum-k,0)个逆序对

（3）统计逆序对的朴素算法是n^2的复杂度，归并法用nlogn的复杂度就可以解决。

（4）网上对于归并法的介绍很多，但是我看到的博客只有一篇看懂了，大多数都没有仔细说，这里我就介绍一遍归并求逆序对的方法。

假如我们要将两个有序（从小到大）数列Array[l,m],Array[m+1,r]合并成一个的有序数列，我们可以这样做。用p指向第一个数组的首位，用q指向第二个数组的首位，用cur指向临时数组的首位，每次把小的那一个插到临时数组的末尾，同时移动指针，这样最后临时数组就是一个有序的了。操作过程中，当A[p]<=A[q]时，t[cur++]=A[p++]（A[p]更小，就将A[p]插到t的末尾），当A[p]>A[q]时，由于A是从小到大排列的，A[p,m]>A[q]，所以在l~m之间有m-p+1个数可以和A[q]构成逆序对（对于任意位置上的那个数，每次都只会扫到位置在他前面且值比他大的数，而且每次一旦扫到，那个位置在他前面且值比他大的数在临时数组里就会放到他的后面，保证不会重复计算到），接着插入临时数组t[cur++]=A[q++]。

（5）本题还有树状数组的解法，比较容易理解，所以再介绍一遍树状数组的。

首先10^9的范围太大了，所以将数值离散化成10^5的，方法就是先排序，再去除重复的值。原数组从后到前扫描一遍复杂度为n，对于每个数，用树状数组看在他后面有多少个比他小的数的复杂度时logn，这样总的复杂度是nlogn。

 

代码案例：

#include
       
        using namespace std;const int MAXN=111111;long long int arr[MAXN];long long int co=0;template
        
         void __shipUp(T arr[],int l,int mid,int r){    T aux[r-l+1];    for(int i=l;i<=r;i++){        aux[i-l]=arr[i];    }    int k=mid+1;    int i=l;    for(int j=l;j<=r;j++){        if(i>mid){            arr[j]=aux[k-l];            k++;        }else if(k>r){            arr[j]=aux[i-l];            i++;        }else if(aux[i-l]<=aux[k-l]){            arr[j]=aux[i-l];            i++;        }else{            arr[j]=aux[k-l];            k++;            co+=mid+1-i;        }    }}template
         
          void __mergesort(T arr[],int l,int r){    if(l>=r)        return;    int mid=(l+r)/2;    __mergesort(arr,l,mid);    __mergesort(arr,mid+1,r);    __shipUp(arr,l,mid,r);}template
          
           void mergesort(T arr[], int n){    __mergesort( arr , 0 , n-1 );}int main(){    int n,m;    long long int k;    while(cin>>n>>m){        for(int i=0;i
           
            >k;            arr[i]=k;        }        mergesort<__int64>(arr,n);        //for(int i=0;i