D - Inversion

左手的ㄟ右手 2021-10-01 00:52 296阅读 0赞

# D - Inversion  #

bobo has a sequence a 1,a 2,…,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>aj.

### Input ###

The input consists of several tests. For each tests:   
  
The first line contains 2 integers n,k (1≤n≤10 5,0≤k≤10 9). The second line contains n integers a 1,a 2,…,a n (0≤a i≤10 9).

### 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是几。

归并讲解：

[https://blog.csdn.net/qq\_42217376/article/details/81224001][https_blog.csdn.net_qq_42217376_article_details_81224001]

会求逆序数后就好做了

AC代码：

#include<bits/stdc++.h>
    #include<algorithm>
    using namespace std;
    long long a[100000],b[100000];
    long long times; 
    void Merge(int s,int m,int e)
    {
    	int p=0;
    	int p1=s,p2=m+1;
    	while(p1<=m&&p2<=e)
    	{
    		if(a[p1]<=a[p2])
    			b[p++]=a[p1++];
    		else
    		{
    			b[p++]=a[p2++];
    			times+=m-p1+1;
    		} 
    	}
    		while(p1<=m)
    			b[p++]=a[p1++];
    		while(p2<=e)
    			b[p++]=a[p2++];
    		for(int i=0;i<e-s+1;i++)
    			a[s+i]=b[i];	
    }
    void Merge_sort(int s,int e)
    {
    	if(s<e)
    	{
    		int m=s+(e-s)/2;
    		Merge_sort(s,m);
    		Merge_sort(m+1,e);
    		Merge(s,m,e);
    	}
    }
    int main()
    {
    	long long n,k;
    	while(~scanf("%I64d%I64d",&n,&k))
    	{
    		for(int i=0;i<n;i++)
    		scanf("%lld",&a[i]);
    		times=0;
    		Merge_sort(0,n-1);
    		if(times-k>0)
    			printf("%I64d\n",times-k);
    		else
    			printf("0\n");
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/zut-syp/p/10543716.html

[https_blog.csdn.net_qq_42217376_article_details_81224001]: https://blog.csdn.net/qq_42217376/article/details/81224001