Inversion

题目链接：

http://acm.hust.edu.cn/vjudge/contest/121349#problem/A

Description

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>a j.

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

##题意：

对有n个元素的数组进行不超过k次操作，每次操作允许交换相邻元素;
求操作后能得到的整个数组的最小逆序数.

##题解：

容易得出每次交换相邻元素最多只能使得逆序数降低1.
而对于一个逆序数不为0的数组，一定存在相邻的两个数满足(i

##代码：
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define maxn 101000
#define mod 100000007
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;

LL num[maxn];

LL _count=0;

void merge_array(int left,int mid,int right)

{

int temp[right-left+1];int k=0;

int i=left;int j=mid+1;

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

{

if(num[i]<=num[j])

temp[k++]=num[i++];

else

{temp[k++]=num[j++];_count+=mid-i+1;}

}

while(i<=mid)

temp[k++]=num[i++];

while(j<=right)

temp[k++]=num[j++];

for(i=left;i<=right;i++)

    num[i]=temp[i-left];

}

void merge_sort(int left,int right)

{

if(left<right)

{

int mid=left+(right-left)/2;

merge_sort(left,mid);

merge_sort(mid+1,right);

merge_array(left,mid,right);

}

}

int main(void)

{

//IN;

int n;

LL k;

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

{

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

        scanf("%I64d",&num[i]);

    _count=0;

    merge_sort(0, n-1);

    printf("%I64d\n", max(_count-k,0LL));

}

return 0;

}

巴特西

HDU 4911 Inversion （逆序数归并排序）

Inversion

题目链接：

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

HDU 4911 Inversion （逆序数 归并排序）

Inversion

题目链接：

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

HDU 4911 Inversion （逆序数归并排序）