[USACO 2016 Feb S]Load Balancing

NC24045. [USACO 2016 Feb S]Load Balancing

描述

Farmer John's N cows are each standing at distinct locations (x1,y1)…(xn,yn) on his two-dimensional farm (1≤N≤1000, and the xi's and yi's are positive odd integers of size at most 1,000,000). FJ wants to partition his field by building a long (effectively infinite-length) north-south fence with equation x=a (a will be an even integer, thus ensuring that he does not build the fence through the position of any cow). He also wants to build a long (effectively infinite-length) east-west fence with equation y=b, where b is an even integer. These two fences cross at the point (a,b), and together they partition his field into four regions.
FJ wants to choose a and b so that the cows appearing in the four resulting regions are reasonably "balanced", with no region containing too many cows. Letting M be the maximum number of cows appearing in one of the four regions, FJ wants to make M as small as possible. Please help him determine this smallest possible value for M.

输入描述

The first line of the input contains a single integer, N. The next N lines each contain the location of a single cow, specifying its x and y coordinates.

输出描述

You should output the smallest possible value of M that FJ can achieve by positioning his fences optimally.

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 8ms, 内存消耗: 384K, 提交时间: 2020-12-13 20:01:55

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define maxn 1005
using namespace std;
struct node{
    int x,y;
}a[maxn],b[maxn];
int c[maxn],top,L,R,l,r,now;
int n,m,ans=0x7fffffff;
bool cmp1(node u,node v){return u.x<v.x;}
bool cmp2(node u,node v){return u.y<v.y;}
void cfb(int k){
    l=r=L=R=0;
    for(int i=1;i<=n;i++){
        if(a[i].x<k)l++;
        else r++;
    }
    now=1;
    for(int i=1;i<=top;i++){
        int kk=c[i]+1;
        for(;now<=n&&b[now].y<=kk;now++){
            if(b[now].x<k)L++;
            else R++;
        }
        ans=min(ans,max(max(L,l-L),max(R,r-R)));
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y),b[i]=a[i];
    sort(a+1,a+n+1,cmp1);
    sort(b+1,b+n+1,cmp2);
    for(int i=1;i<=n;i++)if(b[i].y!=c[top])c[++top]=b[i].y;
    for(int i=1;i<=n;i++)cfb(a[i].x+1);
    printf("%d",ans);
}