- 火柴排队
- 2014-08-04 15:47:45 @
使用归并做的逆序对为什么会超时啊……有没有大神帮小弟看一下……
###------------------------------分割线--------------------------------------------
#include <iostream>
#include <cstring>
using namespace std;
long c[100001],d[100001];
long s=0;
void Qsort(long l,long r)
{
long i,j,k,mid;
mid=c[(l+r)/2];
i=l; j=r;
while (i<=j){
while (c[i]<mid) i++;
while (c[j]>mid) j--;
if (i<=j){
k=c[i];
c[i]=c[j];
c[j]=k;
k=d[i];
d[i]=d[j];
d[j]=k;
i++;
j--;
}
}
if (l<j) Qsort(l,j);
if (i<r) Qsort(i,r);
}
void sort(long l,long mid,long r)
{
long i,j,k;
for (i=l;i<=mid;i++)
for (j=r;j>=mid+1;j--){
if (c[i]>c[j]){
s=(s+j-mid)%99999997;
break;
}
}
i=l;
j=mid+1;
for (k=l;k<=r;k++){
if ((c[i]<c[j] && i<=mid) || (j>r)){
d[k]=c[i];
i++;
}else {
d[k]=c[j];
j++;
}
}
for (i=l;i<=r;i++)
c[i]=d[i];
}
void merge(long l,long r)
{
long mid;
mid=(l+r)/2;
if (l<mid) merge(l,mid);
if (mid+1<r) merge(mid+1,r);
sort(l,mid,r);
}
main()
{
long a1[100001],a2[100001],b1[100001],b2[100001],i,j,n;
cin>>n;
for (i=1;i<=n;i++){
cin>>a1[i];
b1[i]=b2[i]=i;
}
for (i=1;i<=n;i++) cin>>a2[i];
memcpy(c,a1,sizeof(a1)); memcpy(d,b1,sizeof(b1));
Qsort(1,n);
memcpy(a1,c,sizeof(a1)); memcpy(b1,d,sizeof(b1));
memcpy(c,a2,sizeof(a2)); memcpy(d,b2,sizeof(b2));
Qsort(1,n);
memcpy(a2,c,sizeof(a2)); memcpy(b2,d,sizeof(b1));
for (i=1;i<=n;i++){
a1[b1[i]]=i; a2[b2[i]]=i;
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (a1[i]==a2[j]){ a1[i]=j; break;}
memcpy(c,a1,sizeof(c));
merge(1,n);
cout<<s;
}
4 条评论
-
逸仔嘿 LV 4 @ 2014-08-11 10:01:29
..
-
2014-08-07 15:20:25@
...
-
2014-08-06 20:39:03@
...
-
2014-08-04 21:04:42@
有没有人啊
啊啊啊啊啊……
....
- 1
信息
- ID
- 1842
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 5085
- 已通过
- 1102
- 通过率
- 22%
- 被复制
- 10
- 上传者