51Nod 1019 逆序数 【分治】
程序员文章站
2022-05-08 18:06:12
...
1019 逆序数
如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。给出一个整数序列,求该序列的逆序数。
收起
输入
第1行:N,N为序列的长度(n <= 50000) 第2 - N + 1行:序列中的元素(0 <= A[i] <= 10^9)
输出
输出逆序数
输入样例
4 2 4 3 1
输出样例
4
刚拿到这个题的时候想简单了 直接暴力** 结果 TLE 然后就懵了 (手动笑哭) 暴力的先入为主的思想挥之不去 后来又想的从后往前排序 想一想 跟暴力差不多 时间复杂度还是N方 最后想到了 归并排序 如果 第二队的元素入列 第一组剩余元素个数就是第二个元素在 范围内的逆序数 这样就很简单的 代码也就是一个 改进后的 归并排序 废话不多说 上代码
#include<iostream>
using namespace std;
const int MAX_N = 50000+5;
int arr[MAX_N];
int temp[MAX_N];
int ans;
void slove(int left,int right){
if(left < right){
int mid = (left+right)/2;
// 拆分
slove(left,mid);
slove(mid+1,right);
int i = left;
int l = left;
int j = mid +1;
//将两个部分其中一个排完
while(i <= mid && j <= right){
if(arr[i]<= arr[j]){
temp[l++]=arr[i++];
}else{
temp[l++]=arr[j++];
ans+= mid-i+1;
}
}
//确保两个部分所有元素都排完
while(i <= mid){
temp[l++] = arr[i++];
}
while(j <= right){
temp[l++] = arr[j++];
}
//更新序列 为下一步排序做准备
for(i = left; i <= right;i++){
arr[i] = temp[i];
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i = 0; i < n; i++){
cin >> arr[i];
}
ans = 0;
slove(0,n-1);
printf("%d\n",ans);
return 0;
}
上一篇: python网络爬虫入门(一)