2014 HDU多校弟五场A题 【归并排序求逆序对】

这题是2Y,第一次WA贡献给了没有long long 的答案QAQ

题意不难理解,解题方法不难。

先用归并排序求出原串中逆序对的个数然后拿来减去k即可,如果答案小于0,则取0

学习了归并排序求逆序对的方法,可以拿来当模板 TVT

贴代码了:

 #include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm> #define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = ;
const int N = ; int a[N],tmp[N];
//int array_a[N], array_b[N];
ll ans;
int n, k; void Merge(int l,int m,int r)
{
int i = l;
int j = m + ;
int k = l;
while(i <= m && j <= r)
{
if(a[i] > a[j])
{
tmp[k++] = a[j++];
ans += m - i + ;
}
else
{
tmp[k++] = a[i++];
}
}
while(i <= m) tmp[k++] = a[i++];
while(j <= r) tmp[k++] = a[j++];
for(int i=l;i<=r;i++)
a[i] = tmp[i];
} void Merge_sort(int l,int r)
{
if(l < r)
{
int m = (l + r) >> ;
Merge_sort(l,m);
Merge_sort(m+,r);
Merge(l,m,r);
}
} int main()
{
int i, j;
while(EOF != scanf("%d%d",&n,&k)){
for(i=;i<n;i++){
scanf("%d",&a[i]);
//array_a[i] = array_b[i] = a[i];
}
ans = ;
Merge_sort(,n-);
ans -= k;
if(ans <= ) printf("0\n");
else cout << ans << endl;
}
return ;
}
上一篇:AlloyTouch实现下拉刷新


下一篇:Android基本控件之listView(三)<用ListView实现分页加载>