P3138 [USACO16FEB]负载平衡Load Balancing_Silver

    • 237通过
    • 549提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 前缀和 枚举,暴力 线段树 USACO 2016 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Farmer John's $N$ cows are each standing at distinct locations $(x_1, y_1) \ldots (x_n, y_n)$ on his two-dimensional farm ($1 \leq N \leq 1000$, and the $x_i$'s and $y_i$'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: 复制
    7
    7 3
    5 5
    7 13
    3 1
    11 7
    5 3
    9 1
    输出样例#1: 复制
    2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。