社区讨论
为什么用结构体排序是错的?
P1966[NOIP 2013 提高组] 火柴排队参与者 5已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mi6zik2b
- 此快照首次捕获于
- 2025/11/20 13:22 4 个月前
- 此快照最后确认于
- 2025/11/20 13:22 4 个月前
如标题
难道求的不是 当a序列有序时,此时b序列所对应的数字的逆序对的个数吗?
CPP#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct match{
long h,p;
}a1[100001],a2[100001];
long n,b[100001]={0},c[100001]={0};
long long ans=0;
bool com(match x,match y)
{
return x.h<y.h;
}
void msb(int l,int r)
{
if(l==r) return;
int m=(l+r)/2;
msb(l,m);
msb(m+1,r);
int i=l,j=m+1,t=1;
while(i<=m || j<=r)
{
if((b[i]<=b[j] || j>r) && i<=m)
{
c[t]=b[i];
t++;
i++;
continue;
}
if((b[i]>b[j] || i>m) && j<=r)
{
c[t]=b[j];
t++;
j++;
if(i<=m)
ans=(ans+m-i+1)%99999997;
continue;
}
}
for(i=l;i<=r;i++)
b[i]=c[i-l+1];
return;
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
{
scanf("%ld",&a1[i].h);
a1[i].p=i;
}
for(i=1;i<=n;i++)
{
scanf("%ld",&a2[i].h);
a2[i].p=i;
}
sort(a1+1,a1+n+1,com);
sort(a2+1,a2+n+1,com);
for(i=1;i<=n;i++)
b[a1[i].p]=a2[i].p;
msb(1,n);//归并求逆序列 , 在模板题里面A了
cout<<ans;
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...