The Number of Inversions(逆序数)
2024-10-08 08:52:49
For a given sequence A={a0,a1,...an−1}A={a0,a1,...an−1}, the number of pairs (i,j)(i,j) where ai>ajai>aj and i<ji<j, is called the number of inversions. The number of inversions is equal to the number of swaps of Bubble Sort defined in the following program:
bubbleSort(A)
cnt = 0 // the number of inversions
for i = 0 to A.length-1
for j = A.length-1 downto i+1
if A[j] < A[j-1]
swap(A[j], A[j-1])
cnt++ return cnt
For the given sequence AA, print the number of inversions of AA. Note that you should not use the above program, which brings Time Limit Exceeded.
Input
In the first line, an integer nn, the number of elements in AA, is given. In the second line, the elements aiai (i=0,1,..n−1i=0,1,..n−1) are given separated by space characters.
output
Print the number of inversions in a line.
Constraints
- 1≤n≤200,0001≤n≤200,000
- 0≤ai≤1090≤ai≤109
- aiai are all different
Sample Input 1
5
3 5 2 1 4
Sample Output 1
6
Sample Input 2
3
3 1 2
Sample Output 2
2
已知逆序数等于冒泡排序的序列,但这题冒泡排序肯定超时。这题用归并排序优化一下就行。
AC代码
#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;
#define MAX 500000
#define INF 2e9
int L[MAX/+],R[MAX/+];
long long cnt=;
long long merge(int A[],int n,int left,int mid,int right)
{
long long cnt=;
int n1=mid-left;
int n2=right-mid;
for(int i=;i<n1;i++)
{
L[i]=A[left+i];
}
for(int i=;i<n2;i++)
{
R[i]=A[mid+i];
}
L[n1]=INF;
R[n2]=INF;
int i=,j=;
for(int k=left;k<right;k++)//合并
{
if(L[i]<=R[j])
A[k]=L[i++];
else
{
A[k]=R[j++];
cnt=cnt+(n1-i);
}
}
return cnt;
}
long long mergeSort(int A[],int n,int left,int right)
{
long long v1,v2,v3;
if(left+<right)
{
int mid=(left+right)/;
v1=mergeSort(A,n,left,mid);
v2=mergeSort(A,n,mid,right);
v3=merge(A,n,left,mid,right);
return (v1+v2+v3);
}
else
return ;
}
int main()
{
int A[MAX],n;
cnt=;
cin>>n;
for(int i=;i<n;i++)
cin>>A[i];
cnt=mergeSort(A,n,,n);
cout<<cnt<<endl;
return ;
}
最新文章
- nginx服务傻瓜搭建
- Oracle锁的机制
- ios-滚动视图滚动取消键盘
- 制作便携版 FireFox 火狐浏览器
- JS 循环遍历JSON数据
- IOS中如果使用RGB实现背景色
- 修改cmd字体为Consolas
- iOS9中通过UIStackView实现类似大众点评中的效果图
- Angular.js VS. Ember.js:谁将成为Web开发的新宠?
- Database SQL script automation management tools investigation
- A. Grasshopper And the String(CF ROUND 378 DIV2)
- 网络请求 get post
- x01.Weiqi.13: 鼎力推荐
- jquery弹出窗口选择回写值
- 电脑装windows和ubuntu,如何卸载ubuntu系统
- 第六篇--Ubuntu画图软件
- Leetcode 两数之和 (散列表)
- Python基础教程-第3版(文字版) 超清文字-非扫描版 [免积分、免登录]
- Python 读取数据
- (通用)Android App代码混淆终极解决方案【转】