ISSAC


私信TA

用户名:uq_50089742160

访问量:1054

签 名:

等  级
排  名 310
经  验 3453
参赛次数 8
文章发表 8
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

解题思路:


给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数目。

输入

第一行,一个数 n,表示序列中有 n个数。

第二行 n 个数,表示给定的序列。序列中每个数字不超过 int 所表示的范围。

输出

所有逆序对总数。

样例输入

4
3 2 3 2

样例输出

3

提示

数据经过加强!!!

对于 25% 的数据,n≤2500

对于 50% 的数据,n≤4×104。

对于所有数据,n≤5×105

请使用较快的输入输出



这里数据是经过加强的,求逆序对一般有两种做法,一种是线段树和树状数组,还有

一种是归并排序。这里建议使用树状数组。而不建议使用线段树。我在尝试使用归并

排序的时候时间超限了。。。

注意事项:


1.这里数据范围是整形,但数组开不了那么大,所以要使用离散化处理

2.题目要求要快速输入。

3.在数组范围大的时候,建议不要使用memset来初始化,建议嵌套在输入循环语句中初始化,

不然很容易时间超限。



参考代码:

//  求逆序对,树状数组
//  需要离散化 
#include <iostream>
#include <algorithm>
using namespace std;
int tree[500005];
int A[500005],B[500005];
int n;
int cnt = 1;
//快速输入代码 
int read() {
char ch = getchar();
int num = 0;
bool fl = 0;
for(; !isdigit(ch); ch = getchar())
if (ch=='-') fl = 1;
for(; isdigit(ch); ch = getchar())
num = (num<<1)+(num<<3)+ch-48;
if(fl) num = -num;
return num;
}
int lowbit(int k)
{
return k&(-k);
}
void updata(int k,int num)
{
  while(k<=cnt)
  {
  tree[k]+=num;
  k+=lowbit(k);
  }
} 
int getsum(int k)
{
int ans = 0;
while(k)
{
ans+=tree[k];
k-=lowbit(k);
}
return ans;
}
int getnum(int t,int ri)
{
int le = 1;
int mid=(le+ri)/2;
while(le<ri)
{
if(B[mid]==t) return (mid);
else if(B[mid]>t)
{
ri = mid-1;
mid=(le+ri)/2;
}
else
{
le=mid+1;
mid=(le+ri)/2;
}
}
}
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{   
A[i] =read();
B[i] = A[i];
}
//离散化处理
sort(B+1,B+n+1);
tree[1] = 0;
for(int i =2;i<=n;i++)
{
if(B[i]!=B[i-1]) 
{
B[++cnt] = B[i];
tree[cnt] = 0;
}
}
int t;
long long sum = 0;
for(int i = 1;i<=n;i++)
{
int t =getnum(A[i],cnt);
//cout<<t<<endl;
updata(t,1);
sum = sum+(i-getsum(t));
}
printf("%lld",sum);
return 0;
 }


 

0.0分

3 人评分

  评论区

如果用常规的迭代的话,用两个for语句,来循环比较所有的元素,是不是会超时
2020-11-26 18:55:20 | |
  • «
  • 1
  • »