社区讨论

为什么用结构体排序是错的?

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 条回复,欢迎继续交流。

正在加载回复...