P1824 进击的奶牛
2018-06-17 22:00:52来源:未知 阅读 ()
题目描述
Farmer John建造了一个有N(2<=N<=100,000)个隔间的牛棚,这些隔间分布在一条直线上,坐标是x1,...,xN (0<=xi<=1,000,000,000)。
他的C(2<=C<=N)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗,Farmer John想把这些牛安置在指定的隔间,所有牛中相邻两头的最近距离越大越好。那么,这个最大的最近距离是多少呢?
输入输出格式
输入格式:
第1行:两个用空格隔开的数字N和C。
第2~N+1行:每行一个整数,表示每个隔间的坐标。
输出格式:
输出只有一行,即相邻两头牛最大的最近距离。
输入输出样例
5 3 1 2 8 4 9
3
二分答案+隔板法
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int MAXN=100001; 5 inline void read(int &n) 6 { 7 char c=getchar();bool flag=0;n=0; 8 while(c<'0'||c>'9') c=='-'?flag==1,c=getchar():c=getchar(); 9 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar(); 10 } 11 int n,c; 12 int a[MAXN]; 13 int pd(int val) 14 { 15 int now=a[1],tot=c-1; 16 for(int i=2;i<=n;i++) 17 if(a[i]-now>=val) 18 now=a[i],tot--; 19 if(tot<=0) return 1; 20 else return 0; 21 } 22 int main() 23 { 24 read(n);read(c); 25 for(int i=1;i<=n;i++) read(a[i]); 26 sort(a+1,a+n+1); 27 int l=0,r=a[n]; 28 int ans; 29 while(l<=r) 30 { 31 int mid=l+r>>1; 32 if(pd(mid)) 33 l=mid+1,ans=mid; 34 else 35 r=mid-1; 36 } 37 printf("%d",ans); 38 return 0; 39 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 长乐培训Day3 2019-08-16
- 进击的贪吃蛇(一) 2018-06-18
- 1405 奶牛的旅行 2018-06-17
- 3122 奶牛代理商 VIII 2018-06-17
- P2858 [USACO06FEB]奶牛零食Treats for the Cows 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash