HDU4911-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>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

分析：

题意：
求给出数列的逆序数经过K次冒泡交换后还剩多少个逆序对？

解析：
这道题有两种解法：
（1）树状数组：这就是裸题了
（2）分治法

树状数组：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 100005

using namespace std;

struct node{
	int v,id;
};

node book[N];
long long tree[N];
int val[N];
int Max;

bool cmp(node a,node b)
{
	return a.v<b.v;
}

int lowbit(int x)
{
	return x&-x;
}

void updata(int x)
{
	while(x<=Max)
	{
		tree[x]++;
		x+=lowbit(x);
	}
}

long long Sum(int x)
{
	long long sum=0;
	while(x>0)
	{
		sum+=tree[x];
		x-=lowbit(x);
	}
	return sum;
}

long long query(int x)
{
	return Sum(Max)-Sum(x);
}

int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		long long sum=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&book[i].v);
			book[i].id=i;
		}
		sort(book+1,book+n+1,cmp);
		int t=val[book[1].id]=1;
		for(int i=2;i<=n;i++)
		{
			if(book[i].v!=book[i-1].v)
				t++;
			val[book[i].id]=t;
		}
		Max=t;
		for(int i=1;i<=n;i++)
		{
			sum+=query(val[i]);
			updata(val[i]);
		}
		if(sum<=m)
			printf("0\n");
		else
			printf("%lld\n",sum-m);
		memset(tree,0,sizeof(tree));
	}
	return 0;
 } 

分治法：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 100005
 
using namespace std;
 
int book[N],help[N];
long long sum;
 
void solve(int *book,int l,int m,int r)
{
    int l1=l,l2=m+1,c=l;
    while(l1<=m && l2<=r)
    {
        if(book[l1]<=book[l2])
            help[c++]=book[l1++];
        else
        {
            help[c++]=book[l2++];
            sum+=m-l1+1;
        }
    }
    while(l1<=m)
        help[c++]=book[l1++];
    while(l2<=r)
        help[c++]=book[l2++];
    for(int i=l;i<=r;i++)
        book[i]=help[i];
}
 
void merge_sort(int *book,int l,int r)
{
    if(l>=r) 
		return;
    int mid=(l+r)>>1;
    merge_sort(book,l,mid);
    merge_sort(book,mid+1,r);
    solve(book,l,mid,r);
}
 
int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&book[i]);
        sum=0;
        merge_sort(book,1,n);
        sum = max(sum-k,0LL);
        printf("%I64d\n",sum);
    }
    return 0;
}