题解 P6172 【[USACO16FEB]Load Balancing P】
Ccliang
·
·
题解
我看到这个题目是真的没思路，然后看题解还只有一个而且没几行讲思路，快哭了QAQ。
为了避免别人也有我这种糟糕的体验，这篇题解诞生了。
先看题目，最大值最小，学过OI的都知道这要用到二分，直接二分枚举答案再check就好了。
再看check要怎么写。
设我们枚举的答案是ans，则我们分出来的每个区域的奶牛都要小于ans显而易见。
我们枚举 y ，用两个树状数组维护 y 上面区域和下面的奶牛数，然后求一个最优的 x。
但是如果直接枚举x，时间复杂度会直接到n^2，很明显不能直接枚举。
再仔细想想，假设我们是从小到大枚举y，那么上面区域的奶牛数会越来越少，下面的奶牛的数量会越来越多，所以对于上面区域，我们从小到大枚举x，设左上区域奶牛数刚好<=ans时x=t1，对于下面区域，我们从大到小枚举x，设左下区域奶牛数刚好<=ans时x=t2，则最优的x就是min(t1,t2)
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
inline int read()
{
int res=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res;
}
struct Cow{
int x,y;
bool operator <(const Cow a) const{
return y<a.y;
}
}c[N];
int n,sb[N],xb[N];
#define lowbit(x) (x)&(-x)
void change(int a[],int x,int k)
{
while(x<=n)
a[x]+=k,x+=lowbit(x);
}
int query(int a[],int x)
{
int res=0;
while(x>0)
res+=a[x],x-=lowbit(x);
return res;
}
bool check(int x)
{
memset(sb,0,sizeof(sb));
memset(xb,0,sizeof(xb));
for(int i=1;i<=n;i++)
change(sb,c[i].x,1);
int st=n,xt=0,zs=1,zx=n;
for(int t,i=1,j=1;i<=n;i=j)
{
while(c[i].y==c[j].y)
change(sb,c[j].x,-1),change(xb,c[j].x,1),st--,xt++,j++;
while(zs<=n&&query(sb,zs)<=x)
zs++;
zs--;
while(zx>0&&query(xb,zx)>x)
zx--;
t=min(zx,zs);
if(xt-query(xb,t)<=x&&st-query(sb,t)<=x)
return true;
}
return false;
}
pair<int,int>p[N];
int tot,mid,l,r,ans;
int main()
{
n=read();
for(int i=1;i<=n;i++)
c[i].x=read(),c[i].y=read(),p[i].first=c[i].x,p[i].second=i;
sort(p+1,p+n+1);
for(int i=1;i<=n;i++)
{
if(p[i].first!=p[i-1].first)
tot++;
c[p[i].second].x=tot;
}
sort(c+1,c+n+1);
l=1,r=n;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}
```