开发者社区> 华山青竹> 正文

Aggressive cows

简介: 总时间限制: 1000ms 内存限制: 65536kB 描述 Farmer John has built a new long barn, with N (2
+关注继续查看
总时间限制: 1000ms 内存限制: 65536kB
描述
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
输入
* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Line i+1 contains an integer stall location, xi
输出
* Line 1: One integer: the largest minimum distance
样例输入
5 3
1
2
8
4
9
样例输出
3
提示
OUTPUT DETAILS:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.

Huge input data,scanf is recommended.
来源
USACO 2005 February Gold

题目OJ链接:http://bailian.openjudge.cn/practice/2456/

题目分析:

(参考http://blog.csdn.net/wuxiushu/article/details/49158843)

题意要表达的是:把C头牛放到N个带有编号的隔间里,使得任意两头牛所在的隔间编号的最小差值最大。例如样例排完序后变成1 2 4 8 9,那么1位置放一头牛,4位置放一头牛,它们的差值为3;最后一头牛放在8或9位置都可以,和4位置的差值分别为4、5,和1位置的差值分别为7和8,不比3小,所以最大的最小值为3。

分析:这是一个最小值最大化的问题。先对隔间编号从小到大排序,则最大距离不会超过两端的两头牛之间的差值,最小值为0。所以我们可以通过二分枚举最小值来求。假设当前的最小值为x,如果判断出最小差值为x时可以放下C头牛,就先让x变大再判断;如果放不下,说明当前的x太大了,就先让x变小然后再进行判断。直到求出一个最大的x就是最终的答案。

本题的关键就在于讨论差值的大小。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<stdio.h>
 4 #include<string.h>
 5 using namespace std;
 6 const int MAX = 100010;
 7 int a[MAX],n,m;
 8 
 9 bool C(int d)
10 {
11     int t = a[0],count = 1;
12     for(int i = 1;i < n;i ++)
13     {
14         if(a[i] - t >= d)
15         {
16             count ++;
17             t=a[i];
18             if(count >= m)
19                 return true;
20         }
21     }
22     return false;
23 }
24 
25 
26 int solve()
27 {
28     int x = 0,y = a[n-1] - a[0];
29     while(x <= y)
30     {
31         int mid=(x+y)/2;
32         if(C(mid))
33             x=mid + 1;
34         else
35             y=mid - 1;
36     }
37     return x - 1;
38 }
39 
40 
41 int main()
42 {
43     while(~scanf("%d%d",&n,&m))
44     {
45         for(int i = 0;i < n;i ++)
46         scanf("%d",&a[i]);
47         sort(a,a+n);
48         printf("%d\n",solve());
49     }
50     return 0;
51 }

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14878 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15762 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19077 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36371 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20273 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
28299 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载