牛客假日团队赛58 - B Load Balancing(Platinum)

B Load Balancing(Platinum)

前言

• 赛时发现此题没有太多AC，就先放着了，事后发现这的确是一道好题

分析

• 画个图了解一下题意
  
  设M为这四个区域中点数的最大数量，求一个划分方案是的M最小
• 正经东西：
  
  那么M=max(a,b,c,d)，如何求到每一个格子中点的数量呢？首先考虑简单一点的——如何维护一个范围内点的数量。这样肯定能用离散+树状数组维护。假设我们将坐标 y 离散，这个树状数组(1号)维护的是纵坐标小于等于 y 的点的数量，那么当前我们知道的即是 c + d ，a + b 。 但是不够啊，我得知道单个的QwQ，不然没法儿算。于是就来了一个方法——枚举横坐标x，将横坐标小于等于 x 的点加入到另一个树状数组(2号)中去 这样的话，就可以直接求得 c ， a 的值，至于 b ， d怎么求就不用说了。
• 大致过程：离散纵坐标，把点加入到一号树状数组，枚举横坐标 x ，把横坐标小于等于 x 的点加入到二号树状数组，在纵坐标上面进行三分，求得最小的M，

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n,cnt,ans;
int p[N],k[N],b[N];
//0,1
struct nkl
{
    int l,r;
}s[N];

inline bool god(nkl xx,nkl yy)
{
    return xx.l<yy.l;
}

inline int lowbit(int x)
{
    return x&(-x);
}

inline void add(int x,int id)
{
    while(x<=cnt)
    {
        if(id==1) ++k[x];
        else ++p[x];
        x+=lowbit(x);
    }
}

inline int find(int x,int id)
{
    int res=0;
    while(x)
    {
        if(id==1) res+=k[x];
        else res+=p[x];
        x-=lowbit(x);
    }
    return res;
}

inline int sum(int x,int tot)
{
    int xx=find(x,0);//左下 
    int yy=tot-xx;//左上 
    int ano=find(x,1)-xx;//右下
    return max(xx,max(yy,max(ano,n-xx-yy-ano)));    
}

inline int get(int tot)
{
    int l=1,r=cnt,res=1e9;
    while(l+1<r)
    {
        int lm=l+(r-l)/3,rm=r-(r-l)/3;
        int xx=sum(lm,tot),yy=sum(rm,tot);
        res=min(res,min(xx,yy));
        if(xx>yy) l=lm+1;
        else r=rm-1;
    }
    return res;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&s[i].l,&s[i].r);
        b[i]=s[i].r;
    }sort(b+1,b+n+1);

    cnt=unique(b+1,b+n+1)-b-1;
    for (int i=1;i<=n;i++)
        s[i].r=lower_bound(b+1,b+cnt+1,s[i].r)-b;
    sort(s+1,s+n+1,god);

    for (int i=1;i<=n;i++) add(s[i].r,1);

    int ans=1e9;
    for (int i=1,now;i<=n;i=now+1)
    {
        now=i;
        while(now<=n&&s[now].l==s[i].l) now++;
        now--;
        for (int j=i;j<=now;j++) add(s[j].r,0);

        ans=min(ans,get(now));
    }

    printf("%d\n",ans);

    return 0;
}