P1824 进击的奶牛
2024-08-25 03:27:04
题目描述
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行:每行一个整数,表示每个隔间的坐标。
输出格式:
输出只有一行,即相邻两头牛最大的最近距离。
输入输出样例
输入样例#1:
5 3
1
2
8
4
9
输出样例#1:
3
二分答案+隔板法
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=;
inline void read(int &n)
{
char c=getchar();bool flag=;n=;
while(c<''||c>'') c=='-'?flag==,c=getchar():c=getchar();
while(c>=''&&c<='') n=n*+c-,c=getchar();
}
int n,c;
int a[MAXN];
int pd(int val)
{
int now=a[],tot=c-;
for(int i=;i<=n;i++)
if(a[i]-now>=val)
now=a[i],tot--;
if(tot<=) return ;
else return ;
}
int main()
{
read(n);read(c);
for(int i=;i<=n;i++) read(a[i]);
sort(a+,a+n+);
int l=,r=a[n];
int ans;
while(l<=r)
{
int mid=l+r>>;
if(pd(mid))
l=mid+,ans=mid;
else
r=mid-;
}
printf("%d",ans);
return ;
}
最新文章
- Memcached集群/分布式/高可用 及 Magent缓存代理搭建过程 详解
- 如何配置使用 Log4j
- iOS开发常用的第三方类库
- Jenkins学习一:Jenkins是什么?
- 【BZOJ】1507: [NOI2003]Editor(Splay)
- CI系统
- [转]简析 IOS 程序图标的设计
- RMQ之ST算法
- c# 多线程 创建对象实例
- SpringMvc 关于 EXCEL
- SUSE12SP3-Mycat(4)rule.xml配置详解
- Apache Storm
- Java框架中Struts和Struts2框架的区别
- vue-实现全选单选
- ARMCC和GCC编译ARM代码的软浮点和硬浮点问题 【转】
- BZOJ.2208.[JSOI2010]连通数(bitset Tarjan 拓扑)
- Ubuntu配置Github并且新建仓库push代码,从已有仓库clone代码,并且push
- centos 7 下 TFTP服务器安装
- LightOJ - 1027 Dangerous Maze 期望
- leetcode 73 矩阵置零 Python
热门文章
- centeros 7开机自动挂载磁盘
- java读取excel文件内容
- 紫书 习题 8-17 UVa 11536 (滑动窗口)
- ZOJ 2601 Warehouse Keeper
- 如何成为一个偷懒又高效的Android开发人员
- spring 、Mybatis配置sql server数据库
- [Typescript] Installing Promise Type Definitions Using the lib Built-In Types
- [Transducer] Make an Into Helper to Remove Boilerplate and Simplify our Transduce API
- 转:移动建站工具(一):分秒钟将Web网站移动化
- django session深入