题目描述

Farmer John's N cows are each standing at distinct locations (x1,y1)…(xn,yn) on his two-dimensional farm (1≤N≤100, and the xi's and yi's are positive odd integers of size at most B). 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.
For the first five test cases, B is guaranteed to be at most 100. In all test cases, B is guaranteed to be at most 1,000,000.

输入描述:

The first line of the input contains two integers, N and B. 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

输入
7 10
7 3
5 5
9 7
3 1
7 7
5 3
9 1
输出
2

解答

暴力枚举

前缀和求出每次的最大值

这样复杂度就是 
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
#define ll long long
int mp[1005][105],sum[105][105],x[105],y[106],lisx[105],lisy[105];
int main()
{
    std::ios::sync_with_stdio(false);
    int n,b,ans=0x3f3f3f3f;
    int i,mm,m,j,totx=0,toty=0;
    scanf("%d %d",&n,&b);
    for(i=1;i<=n;i++){
        scanf("%d %d",&x[i],&y[i]);
        lisx[++totx]=x[i];
        lisy[++toty]=y[i];
    }
    sort(lisx+1,lisx+totx+1);
    sort(lisy+1,lisy+toty+1);
    totx=unique(lisx+1,lisx+totx+1)-lisx;
    toty=unique(lisy+1,lisy+toty+1)-lisy;
    for(i=1;i<=n;i++){
        x[i]=lower_bound(lisx+1,lisx+totx+1,x[i])-lisx;
        y[i]=lower_bound(lisy+1,lisy+toty+1,y[i])-lisy;
        mp[x[i]][y[i]]=1;
    }
    mp[0][0]=0;
    for(i=1;i<=n+1;i++){
        for(j=1;j<=n+1;j++){
            mp[i][j]=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1]+mp[i][j];
        }
    }
    for(i=2;i<=n+1;i++){
        for(j=2;j<=n+1;j++){
            int x=mp[i][j],y=mp[n][j]-x,p=mp[i][n]-x,q=n-x-y-p;
            int tmp=max(x,max(y,max(p,q)));
            ans=min(ans,tmp);
        }
    }
    printf("%d\n",ans);
 
 return 0;
}

来源：甦萌