社区讨论

求助映射哪里出问题了

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

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@lo7qoklw
此快照首次捕获于
2023/10/27 06:11
2 年前
此快照最后确认于
2023/10/27 06:11
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
#define MAXN 100005
int n,a[MAXN],b[MAXN],c[MAXN],d[MAXN],e[MAXN];
long long ret;
void Divide(int l,int r)
{
	if(l==r)
	    return;
	int m=(l+r)/2;
	Divide(l,m);
	Divide(m+1,r);
	for(int i=l,j=m+1,k=l;i<=m||j<=r;)
	    if(i<=m&&(j>r||a[i]<=a[j]))
	    	e[k++]=a[i++],ret+=j-m-1;
		else
		    e[k++]=a[j++];
	for(int i=l;i<=r;i++)
	    a[i]=e[i];
	return ;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        c[i]=a[i]=read();
    for(int i=1;i<=n;i++)
        d[i]=b[i]=read();
    sort(c+1,c+n+1);
    sort(d+1,d+n+1);
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(c+1,c+n+1,a[i])-c;
    for(int i=1;i<=n;i++)
        b[i]=lower_bound(d+1,d+n+1,b[i])-d;
    for(int i=1;i<=n;i++)
        a[i]=b[a[i]];
    Divide(1,n);
    printf("%lld\n",ret);
    return 0;
}
rt,有点绕,人傻了

回复

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

正在加载回复...