当前位置：首页 > news >正文

洛谷——P2862 [USACO06JAN]把牛Corral the Cows

news 来源：原创 2024/5/9 14:35:54

P2862 [USACO06JAN]把牛Corral the Cows

题目描述

Farmer John wishes to build a corral for his cows. Being finicky beasts, they demand that the corral be square and that the corral contain at least C (1 <= C <= 500) clover fields for afternoon treats. The corral's edges must be parallel to the X,Y axes.

FJ's land contains a total of N (C <= N <= 500) clover fields, each a block of size 1 x 1 and located at with its lower left corner at integer X and Y coordinates each in the range 1..10,000. Sometimes more than one clover field grows at the same location; such a field would have its location appear twice (or more) in the input. A corral surrounds a clover field if the field is entirely located inside the corral's borders.

Help FJ by telling him the side length of the smallest square containing C clover fields.

约翰打算建一个围栏来圈养他的奶牛.作为最挑剔的兽类，奶牛们要求这个围栏必须是正方形的，而且围栏里至少要有C< 500)个草场，来供应她们的午餐.

约翰的土地上共有C<=N<=500)个草场，每个草场在一块1x1的方格内，而且这个方格的坐标不会超过10000.有时候，会有多个草场在同一个方格内，那他们的坐标就会相同.

告诉约翰，最小的围栏的边长是多少？

输入输出格式

输入格式：

Line 1: Two space-separated integers: C and N

Lines 2..N+1: Each line contains two space-separated integers that are the X,Y coordinates of a clover field.

输出格式：

Line 1: A single line with a single integer that is length of one edge of the minimum size square that contains at least C clover fields.

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

Explanation of the sample:

|* *

| * *

+------Below is one 4x4 solution (C's show most of the corral's area); many others exist.

|CCCC

|*CCC*

|C*C*

+------

什么？！这道题做过？！啊啊啊、、、蒟蒻表示忘记了、、、

http://www.cnblogs.com/z360/p/7641389.html

二分答案

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 5010
using namespace std;
int c,n,mid,ans,tmp[N];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
struct Node
{
    int x,y;
}node[N];
int cmp(Node a,Node b){return a.x<b.x;}
int work(int l,int r)
{
    if(r-l+1<c) return false;
    int sum=0;
    for(int i=l;i<=r;i++)
     tmp[++sum]=node[i].y;
    sort(tmp+1,tmp+1+sum);
    for(int i=c;i<=sum;i++)
     if(tmp[i]-tmp[i-c+1]<=mid) return true;
    return false;
}
int pd(int x)
{
    int l=1,r;
    for(r=1;r<=n;r++)
    {
        if(node[r].x-node[l].x>x) 
        {
            if(work(l,r-1)) return true;
            while(node[r].x-node[l].x>x) l++;
        }
    }
    if(work(l,n)) return true;
    return false;
}
int main()
{
    c=read(),n=read();
    for(int i=1;i<=n;i++)
     node[i].x=read(),node[i].y=read();
    sort(node+1,node+1+n,cmp);
    int L=0,R=10000;
    while(L<=R)
    {
        mid=(L+R)>>1;
        if(pd(mid)) ans=mid+1,R=mid-1;
        else L=mid+1;
    }
    printf("%d",ans);
    return 0; 
}