社区讨论

求大神更正

P1966[NOIP 2013 提高组] 火柴排队参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi4hoxp6
此快照首次捕获于
2025/11/18 19:27
4 个月前
此快照最后确认于
2025/11/18 19:27
4 个月前
查看原帖
CPP
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAXN 100010
int s[MAXN],r1[MAXN],p=0;
struct jg
{
    int x,y;
}a[100010],b[100010];
bool cmp(jg a,jg b)
{
    return a.x<b.x;
}
void mergesort(int l,int r)
{
    int m,k=l,w=(l+r)/2,q=l;
    if(l==r) return;
    m=(l+r)/2;
    mergesort(1,m);
    mergesort(m+1,r);
    while(q<=m&&w<=r)
    {
        if(s[q]>s[w])
        {
            p=(p+m-q+1)%99999997;
            r1[k]=s[w];
            k++;
            w++;
        }
        else
        {r1[k]=s[q];
         k++;
         q++;}
    }
    while(q<=m)
    {
        r1[k]=s[q];
            k++;
            q++;
    }
    while(w<=r)
    {
        r1[k]=s[w];
        k++;
        w++;
    }
    for(int i=l;i<=r;i++)
    s[i]=r1[i];
}
int main()
{
    int n,j;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&j);
        a[i].x=j;
        a[i].y=i;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&j);
        b[i].x=j;
        b[i].y=i;
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++)
    s[a[i].y]=b[i].y;
    mergesort(1,n);
    cout<<p%99999997;
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...