62pts求助
查看原帖
62pts求助
939453
jacky_Shijiaqi楼主2025/2/3 20:41
#include<bits/stdc++.h>
using namespace std;

int q[100010];
int a[100010],b[100010],b1[100010],b2[100010];
bool cmp1(int x,int y)
{
    return abs(x)<abs(y);
}
bool cmp2(int x,int y)
{
    return abs(x)>abs(y);
}
int l[100010],r[100010],mp[100010],mp1[100010];
int vis[100010],fa[2][100010];
int find(int k,int x)
{
    if(fa[k][x]==x) return x;
    return fa[k][x]=find(k,fa[k][x]);
}
int main()
{
    int n,cur=0,cur1=0;
    cin >>n;
    for (int i=1;i<=n;i++) cin >>a[i];
    for (int i=1;i<=n+5;i++) fa[0][i]=fa[1][i]=i;
    for (int i=1;i<=n;i++)
    {
        cin >>b[i];
        if(b[i]<0)
        {
            b1[++cur]=-b[i];
            mp[cur]=i;
        }
        else
        {
            b2[++cur1]=b[i];
            mp1[cur1]=i;
        }
    }
    sort(b1+1,b1+cur+1);
    sort(b2+1,b2+cur1+1);
    // sort(a+1,a+n+1,cmp1);
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        if(a[i]>0)
        {
            int p=upper_bound(b1+1,b1+cur+1,a[i])-b1;
            int x=find(0,p);
            p=mp[x];
            if(p<=n)
            {
                q[i]=p;
                cnt++;
                fa[0][x]=find(0,x+1);
            }
        }
        else
        {
            int p=lower_bound(b2+1,b2+cur1+1,-a[i])-b2-1;
            int x=find(1,p);
            p=mp1[x];
            if(p>0)
            {
                q[i]=p;
                cnt++;
                fa[1][x]=find(1,x-1);
            }
        }
    }
    cout<<cnt;
    return 0;
}
2025/2/3 20:41
加载中...