题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4911
解题报告： 给出一个长度为n的序列，然后给出一个k，要你求最多做k次相邻的数字交换后，逆序数最少是多少？
因为每次相邻的交换操作最多只能减少一个逆序对，所以最多可以减少k个逆序对，所以我们只要求出原来的序列有多少个逆序对然后减去k再跟0取较大的就可以了。
因为数据范围是10的五次方，所以暴力求肯定会TLE，所以要用n*logn算法求逆序对，n*logn算法有几种可以求逆序对的：
线段树，树状数组，归并排序。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef __int64 INT;
const int maxn = +; struct node
{
int d,cixu;
}A[maxn];
struct Node
{
int l,r;
INT n;
}tree[*maxn];
bool cmp1(node a,node b)
{
if(a.d == b.d) return a.cixu < b.cixu;
return a.d < b.d;
}
bool cmp2(node a,node b)
{
return a.cixu < b.cixu;
}
void build(int p)
{
if(tree[p].l == tree[p].r) return ;
int mid = (tree[p].l + tree[p].r) / ;
tree[*p].l = tree[p].l;
tree[*p].r = mid;
tree[*p].n = tree[*p+].n = ;
tree[*p+].l = mid + ;
tree[*p+].r = tree[p].r;
build(*p);
build(*p+);
}
void insert(int p,int l)
{
tree[p].n++;
if(tree[p].l == tree[p].r) return ;
int mid = (tree[p].l + tree[p].r) / ;
if(l <= mid) insert(*p,l);
else insert(*p+,l);
}
INT query(int p,int l,int r)
{
if(l > r) return ;
if(tree[p].l == l && tree[p].r == r)
return tree[p].n;
int mid = (tree[p].l + tree[p].r) / ;
if(r <= mid) query(*p,l,r);
else if(l <= mid && r > mid)
return query(*p,l,mid) + query(*p+,mid+,r);
else return query(*p+,l,r);
} int main()
{
int n;
INT k;
while(scanf("%d%I64d",&n,&k)!=EOF)
{
tree[].l = ;
tree[].r = n;
tree[].n = ;
build();
for(int i = ;i <= n;++i)
{
scanf("%d",&A[i].d);
A[i].cixu = i;
}
sort(A+,A+n+,cmp1);
int f = ,hehe = 0x7fffffff;
for(int i = ;i <= n;++i)
{
if(A[i].d != hehe)
{
hehe = A[i].d;
f++;
}
A[i].d = f;
}
sort(A+,A+n+,cmp2);
INT ans = ;
for(int i = ;i <= n;++i)
{
ans += query(,A[i].d+,n);
insert(,A[i].d);
}
ans = ans-k > ? (ans-k) : ;
printf("%I64d\n",ans);
}
return ;
}