#include <iostream>
#include <algorithm>
using namespace std;
int cnt = 0; int MOD = 99999997;
struct huochai{ int height; int th; bool operator <(const huochai& op2) const { return height<op2.height; } };
void merge_sorts(int A[],int x,int y)
{
if(y-x>1)
{
int m=x+(y-x)/2;
int p=x,q=m;
merge_sorts(A,x,m);
merge_sorts(A,m,y);
while(p<m||q<y)
{
if(q>=y||(p<m&&A[p]<=A[q]))
p++;
else {
q++;
cnt =(( cnt+(m-p))%MOD);
}
}
}
}
huochai a[100010];
huochai b[100010] ;
int c[100010];
int main()
{
int N;
cin>>N;
for(int i=0;i<N;i++)
{cin>>a[i].height;a[i].th = i;}
for(int i=0;i<N;i++)
{cin>>b[i].height;b[i].th = i;}
sort(a,a+N);
sort(b,b+N);
for(int i=0;i<N;i++)
c[a[i].th]=b[i].th;
merge_sorts(c,0,N-1);
cout<<cnt<<endl;
#ifdef DEBUG
while(1);
#endif
return 0;
}
不知道哪里错了 求解
3 条评论
-
东方幻想 LV 8 @ 2014-11-04 18:36:17
楼下大神的意思是让你改学pascalO(∩_∩)O
-
@ 2014-11-04 21:32:31
Pascal 跟 C++ 有啥区别啊
-
-
@ 2014-11-03 21:34:43
var
t,n,i,j:longint;
ans:int64;
a:array[1..200000,1..4]of longint;
procedure mergot(l,x,r:longint);
var
b:array[1..200000]of longint;
i,j,p:longint;
begin
i:=l;j:=x+1;p:=l;
while p<=r do begin
if (i<=x)and((j>r)or(a[i,4]<=a[j,4]))then begin
b[p]:=a[i,4];inc(i);end else begin
b[p]:=a[j,4];inc(j);ans:=ans+x-i+1;end;inc(p);end;
for i:=l to r do a[i,4]:=b[i];
end;
procedure msort(l,r:longint);
begin
if l>=r then exit;
msort(l,(l+r)shr 1);
msort((l+r)shr 1+1,r);
mergot(l,(l+r)shr 1,r);
end;
procedure swap(var x,y:longint);
var t:longint;
begin
t:=x;x:=y;y:=t;
end;
procedure qsort(l,r,x,y:longint);
var
i,j,mid,t:longint;
begin
i:=l;j:=r;mid:=a[(l+r)shr 1,x];
repeat
while a[i,x]<mid do inc(i);
while a[j,x]>mid do dec(j);
if i<=j then begin swap(a[i,x],a[j,x]);
swap(a[i,x+1+y],a[j,x+1+y]);inc(i);dec(j);end;
until i>j;
if i<r then qsort(i,r,x,y);
if l<j then qsort(l,j,x,y);
end;
begin
read(n);
for i:=1 to n do begin read(a[i,1]);a[i,2]:=i;end;
for i:=1 to n do begin read(a[i,3]);a[i,4]:=i;end;
qsort(1,n,1,0);qsort(1,n,3,0);qsort(1,n,2,1);
ans:=0;
msort(1,n);
writeln(ans mod 99999997);
end.
希望你能看懂 -
@ 2014-11-03 21:27:19
说好的逆序对映射回来乱搞呢
- 1
信息
- ID
- 1842
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 5085
- 已通过
- 1102
- 通过率
- 22%
- 被复制
- 10
- 上传者
-
Towerlight
