洛谷——P2862 [USACO06JAN]把牛Corral the Cows
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.
输入输出样例
说明
Explanation of the sample:
|* *
| * *
+------Below is one 4x4 solution (C's show most of the corral's area); many others exist.
|CCCC
|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() { ,f=;char ch=getchar(); ;ch=getchar();} +ch-',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) { <c) return false; ; for(int i=l;i<=r;i++) tmp[++sum]=node[i].y; sort(tmp+,tmp++sum); for(int i=c;i<=sum;i++) ]<=mid) return true; return false; } int pd(int x) { ,r; ;r<=n;r++) { if(node[r].x-node[l].x>x) { )) 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(); ;i<=n;i++) node[i].x=read(),node[i].y=read(); sort(node+,node++n,cmp); ,R=; while(L<=R) { mid=(L+R)>>; ,R=mid-; ; } printf("%d",ans); ; }
距 NOIp2017 还剩 16 天
你可以做的事情还有很多,即使到最后一秒也不要放弃,因为不到结束的那一刻谁也不知道结果会怎样
最新文章
- Java 8函数编程轻松入门(四)方法引用
- mybatis 一对一与一对多collection和association的使用
- ElasticSearch 嵌套映射和过滤器及查询
- (转) 一步一步学习ASP.NET 5 (二)- 通过命令行和sublime创建项目
- 用nodejs搭建一个简单的服务器
- TCP/IP 协议:链路层概述
- arulesSequences包做序列模式的关联分析
- PUT 还是 POST ?
- poj 1180 斜率优化dp
- MYSQL内存
- PLINQ 简介
- Discuz帖子列表页无法ajax加载下一页问题
- Spring各种注解标签作用详解
- shell学习之字符串处理
- 什么是比特币(Bitcoin)?
- HashMap源码剖析
- jquery.proxy的四种使用场景及疑问
- Oracle之plsql快速入门
- java集合系列——List集合总结(六)
- Basic Git commands
热门文章
- 【Feasibility of Learning】林轩田机器学习基石
- 自动化测试(二)如何用python写一个用户登陆功能
- eclipse集成python(Pydev插件安装)
- Python网络编程(weekly summary1)
- ssh-centos74.sh
- Vue2 全局过滤器(vue-cli)
- poj2388 更水
- 【bzoj2079】[Poi2010]Guilds 构造结论题
- [洛谷P4346][CERC2015]ASCII Addition
- [bzoj3270] 博物馆 [期望+高斯消元]