Problem Description
bobo has a sequence a1,a2,…,an. 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≤iaj.
Input
【hdu4911（Inversion）】The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an (0≤ai≤109).
Output
For each tests:
A single integer denotes the minimum number of inversions.
#include using namespace std;
long long int merge(int *a,int start,int mid,int end,int *t){
int i=start,j=mid+1,k=start;
long long int cnt=0;
while (i<=mid&&j<=end)
{
if(a[i]>a[j]){
t[k++]=a[j++];
cnt+=mid-i+1;
}
else{
t[k++]=a[i++];
}
}
while (i<=mid)
{
t[k++]=a[i++];
}
while (j<=end)
{
t[k++]=a[j++];
}
for (int i=start;
i<=end;
i++)//这里忘了将临时数组的值还回去，这样每次白排序了
{
a[i]=t[i];
}
return cnt;
}
long long intmerge_sort(int *a,int start,int end,int *t ){
int mid;
long long int cnt=0;
if(start==end){
t[start]=a[start];
}
else{
mid=(start+end)/2;
cnt+=merge_sort(a,start,mid,t);
//这里也要加cnt，每个递归的mergeSort的值都要加起来，为防止错误，最好用全局变量
cnt+=merge_sort(a,mid+1,end,t);
cnt+=merge(a,start,mid,end,t);
}
return cnt;
}int main()
{
int n,k;
long long int cnt;
while (cin>>n>>k)
{
int a[n];
int t[n];
for (int i=0;
i>a[i];
}
cnt=merge_sort(a,0,n-1,t);
long long int result=((cnt-k)>=0)?(cnt-k):0;
cout<
注意事项
1.一定要注意数字越界。。。。。int 和long我曹溢出了。。。0≤k≤109，cnt数字很大，longlongint和long，int的区别
推荐阅读
