bzoj4411 [Usaco2016 Feb]Load balancing

bzoj4411 [Usaco2016 Feb]Load balancing

​​ Description

给出N个平面上的点。保证每一个点的坐标都是正奇数。 你要在平面上画两条线，一条是x=a，一条是y=b，且a和b都是偶数。 直线将平面划成4个部分，要求包含点数最多的那个部分点数最少。

Input

第一行一个数N。 接下来N行每行描述一个点 N<=100000 1<=x,y<=1000000

Output

输出一个数表示最少的点数。

Sample Input

7 7 3 5 5 7 13 3 1 11 7 5 3 9 1 Sample Output

2 HINT

Source

枚举横坐标 然后上下维护线段树 然后每次做的时候对于纵坐标二分一个位置

max(l1,l2)>=max(r1,r2) 然后取一下四个中的最大值返回即可 因为前面这个函数是单峰函数所以可以在线段树上直接二分即可

#include#include#include#define lc (x<<1)#define rc (x<<1|1)#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=100010;struct P{ int x,y;}point[N];struct node{int v[2];}tree[N<<3];int d[N],nn,d1[N],n1;inline bool cmp(const P &a,const P &b){return a.x>1; if(p<=mid) insert1(lc,l,mid,p,v,op); else insert1(rc,mid+1,r,p,v,op);}inline int query(int x,int l,int r,int l1,int r1,int l2,int r2){ int mid=l+r>>1; int lv0=tree[lc].v[0],rv0=tree[rc].v[0]; int lv1=tree[lc].v[1],rv1=tree[rc].v[1]; if (l==r) { lv0=tree[x].v[0],rv0=tree[x].v[0]; lv1=tree[x].v[1],rv1=tree[x].v[1]; if (max(l1+lv0,l2+lv1)>=max(r1+rv0,r2+rv1)) r1+=rv0,r2+=rv1;else l1+=lv0,l2+=lv1; return max(max(l1,l2),max(r1,r2)); } if (max(lv0+l1,lv1+l2)>=max(rv0+r1,rv1+r2)) return query(lc,l,mid,l1,rv0+r1,l2,rv1+r2); else return query(rc,mid+1,r,l1+lv0,r1,l2+lv1,r2);}int main(){ freopen("bzoj4411.in","r",stdin); int n=read(); for (int i=1;i<=n;++i) point[i].x=read(),point[i].y=read(),d[++nn]=point[i].y, d1[++n1]=point[i].x;sort(d1+1,d1+n1+1);n1=unique(d1+1,d1+n1+1)-d1-1; sort(d+1,d+nn+1);nn=unique(d+1,d+nn+1)-d-1; for (int i=1;i<=n;++i){ point[i].x=lower_bound(d1+1,d1+n1+1,point[i].x)-d1; point[i].y=lower_bound(d+1,d+nn+1,point[i].y)-d; } sort(point+1,point+n+1,cmp);int now=1,ans=inf; //for (int i=1;i<=n;++i) printf("%d %d\n",point[i].x,point[i].y); for (int i=1;i<=n;++i) insert1(1,1,nn,point[i].y,1,1); for (int i=1;i<=n1;++i){ while(point[now].x==i) insert1(1,1,nn,point[now].y,-1,1),insert1(1,1,nn,point[now].y,1,0),++now; ans=min(ans,query(1,1,nn,0,0,0,0)); }printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。