【题目描述】 Farmer John 的 n 头牛分别站在他的二维农场的不同位置(x1,y1)..(xn,yn)（xi 和 yi 都是正奇数且不大于 B）。为了划分他的农场，约翰想建立两个栅栏（你可以认为它们是无限长的），南北方向一个，表达式为 x=a（a 是一个正偶数，这样可以确保栅栏不会穿过任意一头牛）；东西方向一个，表达式为 y=b，b 也是一个正偶数。这两条栅栏在点(a,b)处相交，并一起把这个农场分为 4 部分。 农夫约翰想要选择一组 a 和 b，使四个区域中的奶牛数都尽量地平衡，即没有一个区域所包含的奶牛的数目过多。现在定义这为 m，约翰想要让 m 尽量地小。请你帮助他算出最小的 m。 【输入格式】 第一行，包含两个整数 N 和 B，表示有 n 头奶牛，以及农场的大小。 接下来 N 行，每行两个整数 xi,yi，表示第 i 头牛的坐标。 【输出格式】 一个整数 m，表示最小的四个区域中包含最多奶牛的区域的奶牛数目。 【样例输入】 7 10 7 3 5 5 9 7 3 1 7 7 5 3 9 1 【样例输出】 2 【数据范围】 1<=n<=1000，B<=maxlongint 【分析】 首先可以设计出暴搜算法：双重循环枚举x=a和y=b，然后再一重循环计算每个区域的点数，最后打擂台即可。但是这种方法显然会TLE。 然后发现这个算法有一个很明显的重复计算： 比如上图的y已经确定，算法1会枚举图中的两条竖线（即x），但是这两条竖线只要一条就够了——因为两条竖线都把两个点划在左边，一个点划在右边，且横线已经固定。于是可以离散化得出算法2，即把算法1的枚举x=a和y=b改成x=xi-1和y=yi-1。
var x,y:array[0..1001]of longint; i,j,k,n,xx,yy,t1,t2,t3,t4,t,ans:longint; begin readln(n,k); for i:=1 to n do readln(x[i],y[i]); ans:=maxlongint; for i:=1 to n do for j:=1 to n do begin xx:=x[i]-1;yy:=y[j]-1; t1:=0;t2:=0;t3:=0;t4:=0; for k:=1 to n do begin if (x[k]<xx)and(y[k]<yy) then inc(t1); if (x[k]>xx)and(y[k]<yy) then inc(t2); if (x[k]<xx)and(y[k]>yy) then inc(t3); if (x[k]>xx)and(y[k]>yy) then inc(t4); end; t:=t1; if t2>t then t:=t2; if t3>t then t:=t3; if t4>t then t:=t4; if t<ans then ans:=t; end; write(ans); end.不幸的是，这样仍然会TLE，因为N最多可达1000。 不难发现，算法2中似乎计算了一些人脑就知道不是最优解的情况，比如 这种情况一定不是最优解，因为竖线的左边一个点都没有。 于是可以设计算法3，一重循环枚举一条竖线（即x=a），然后二分出最优的竖线。先假设每次都可以知道从mid分开后，四个区域内每个区域的点数，那么我们便可以知道二分的方法：如果最大值在上方则l=mid，否则r=mid（边界条件还需要调试）。至于每个区域的点数，可以用前缀和+线段树（树状数组应该也行吧）求出来。
#include<cstdio> #include<algorithm> #include<vector>//为了STL启用C++辣！ using namespace std; const int INF=0xfffffff; const int maxn=500000+10; const int maxm=100000+10; int srchq[maxn],prex[maxn],prey[maxn],left,right,down,up,n,cnt,ok,x,y; bool exist[maxn]; vector<int> which[maxn]; int node[4*maxn]; void Insert(int l,int r,int now,int aim){ node[now]++; if (l==r) return; int m=(l+r)/2; if (aim>m) Insert(m+1,r,now*2+1,aim);else Insert(l,m,now*2,aim); } void Query(int al,int ar,int l,int r,int now){ int m=(l+r)/2; if (al<=l && ar>=r) ok+=node[now]; else { if (al<=m) Query(al,ar,l,m,now*2); if (ar>m) Query(al,ar,m+1,r,now*2+1); } } int Work(int i){ int lmax,rmax,l=left,r=right-1,m,tmp; while(l<r){ m=(l+r)/2; ok=0; Query(left-1,m,left-1,right,1); tmp=ok; lmax=max(tmp,prex[m]-tmp); rmax=max(prey[i]-tmp,n-(prex[m]+prey[i]-tmp)); if (lmax<rmax) l=m+1; else if (lmax==rmax) { r=m; break; } else r=m-1; } ok=0; Query(left-1,r,left-1,right,1); tmp=ok; lmax=max(tmp,prex[r]-tmp); rmax=max(prey[i]-tmp,n-(prex[r]+prey[i]-tmp)); return max(lmax,rmax); } int main(){ left=down=INF; right=up=-INF; scanf("%d%d",&n,&x); for(int i=1;i<=n;i ++){ scanf("%d %d",&x,&y); left=min(left,(x+1)/2); right=max(right,(x+1)/2); down=min(down,(y+1)/2); up=max(up,(y+1)/2); prex[(x+1)/2]++; prey[(y+1)/2]++; if (!exist[(y+1)/2]){ exist[(y+1)/2]=1; srchq[++ cnt]=(y+1)/2; } which[(y+1)/2].push_back((x+1)/2); } for (int i=left;i<=right;i++) prex[i]+=prex[i-1]; for (int i=down;i<=up;i++) prey[i]+=prey[i-1]; int ans=INF; sort(srchq+1,srchq+cnt+1); for (int i=1;i<=cnt-1;i ++) { for (int j=0;j<which[srchq[i]].size();j ++) Insert(left-1,right,1,which[srchq[i]][j]); ans=min(ans,Work(srchq[i])); } printf("%d",ans); return 0; }转载于:https://www.cnblogs.com/JRX2015U43/p/6533500.html
