Total Submission(s): 528    Accepted Submission(s): 228

Problem Description

bobo has a sequence a₁,a₂,…,a_n. He is allowed to swap twoadjacent 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

解法：求的所给序列的逆序数。然后减掉k，假设小于零就去零！

代码例如以下：（归并排序法）

#include<stdio.h>

int is1[112345],is2[112345];// is1为原数组，is2为暂时数组。n为个人定义的长度

__int64 merge(int low,int mid,int high)

{

	int i=low,j=mid+1,k=low;

	__int64 count=0;

	while(i<=mid&&j<=high)

		if(is1[i]<=is1[j])// 此处为稳定排序的关键，不能用小于

			is2[k++]=is1[i++];

		else

		{

			is2[k++]=is1[j++];

			count+=j-k;// 每当后段的数组元素提前时。记录提前的距离

		}

		while(i<=mid)

			is2[k++]=is1[i++];

		while(j<=high)

			is2[k++]=is1[j++];

		for(i=low;i<=high;i++)// 写回原数组

			is1[i]=is2[i];

		return count;

}

__int64 mergeSort(int a,int b)// 下标，比如数组int is[5]，所有排序的调用为mergeSort(0,4)

{

	if(a<b)

	{

		int mid=(a+b)/2;

		__int64 count=0;

		count+=mergeSort(a,mid);

		count+=mergeSort(mid+1,b);

		count+=merge(a,mid,b);

		return count;

	}

	return 0;

}

int main()

{

	int n, x;

	__int64 k;

	__int64 sum;

	while(scanf("%d%I64d",&n,&k)!=EOF)

	{

		for(int i=0;i<n;i++)

		{

			scanf("%d",&x);

			is1[i] = x;

		}

		__int64 ans=mergeSort(0,n-1);

		sum=0;

		printf("%I64d\n",ans-k>0?ans-k:0);

	}

	return 0;

}