题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选

择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终 点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达 终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳 跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能 移走起点和终点的岩石)。

输入输出格式

输入格式:

输入文件名为 stone.in。

输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终 点之间的岩石数,以及组委会至多移走的岩石数。

接下来 N 行,每行一个整数,第 i 行的整数 Di(0 < Di < L)表示第 i 块岩石与 起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同 一个位置。

输出格式:

输出文件名为 stone.out。 输出文件只包含一个整数,即最短跳跃距离的最大值。

输入输出样例

输入样例#1:

25 5 2
2
11
14
17
21
输出样例#1:

4

说明

输入输出样例 1 说明:将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。

另:对于 20%的数据,0 ≤ M ≤ N ≤ 10。 对于50%的数据,0 ≤ M ≤ N ≤ 100。

对于 100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。

--------------------------------------------------------------------------------------------------------------------------------------------------------------

重温一下水题

二分答案 最小值最大

注意细节,并且有一个数据是n=0,m=0,所以r要和L取一下max

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=;
int n,m,L,d[N]; bool check(int dis){
int cnt=,last=,i;
for(i=;i<=n;i++){
if(d[i]-d[last]>=dis) last=i;
else cnt++;
}
if(cnt>m) return false;
if(L-d[last]<dis) return false;
return true;
} int l=,r=;
int main(){
scanf("%d%d%d",&L,&n,&m);
for(int i=;i<=n;i++) {scanf("%d",&d[i]); r=max(r,d[i]);} r=max(L,r);
while(l<r){
int mid=l+(r-l+)/;
if(check(mid)) l=mid;
else r=mid-;
}
cout<<l;
}

最新文章

  1. ajax参数设置略解
  2. 解读HTML 5新语法 提高语义价值
  3. mysql help
  4. sql基础查询语句
  5. C# Index 定义索---引具体使用
  6. MyBatis之七:使用generator工具
  7. ios tableview 上加 textfiled
  8. Android项目代码混淆
  9. 95秀-弹窗+listview+动画 示例
  10. 为ownCloud配置SSL连接
  11. bootstrap 模态框动态加载数据
  12. spring问题排查-调低日志等级
  13. http学习笔记2(URL)
  14. 转:Apache 与 Nginx 比较
  15. .NET Core/.NET之Stream简介
  16. Spring Boot (三)模板引擎FreeMarker集成
  17. 模板-gcd
  18. 同样:Hashtable较HashMap也是如此。
  19. Java - 25 Java 接口
  20. Bootstrap(11)列表组面板和嵌入组件

热门文章

  1. 【Win 10 应用开发】分析 URI 中的查询字符串
  2. JS提交对象数组到服务端的方法总结(C#实例)
  3. 使用vbs脚本进行批量编码转换
  4. JMeter之JMS接口测试
  5. 使用NFC读卡器ACR122u读取银行卡信息
  6. dom4j读写XML文件
  7. 鹿定制|Lu Couture|鹿定制·高级西装礼服私享定制品牌|芙蓉中路明城国际1425
  8. STL中map与hash_map容器的选择收藏
  9. IntentService的使用
  10. Javascript数组中shift()和push(),unshift()和pop()操作方法使用
  11. ichartjs 使用BUG,assign_scale:true 解决
  12. 为什么使用enable_shared_from_this——shared_ptr两类错误
  13. 软件工程——构建之法高分Tips
  14. 详解 Java NIO
  15. 洗礼灵魂,修炼python(12)--python关键词,包
  16. python抓取bing主页背景图片
  17. SpringMVC在使用Jackson2时关于日期类型格式化的问题
  18. VB.NET and C# 差异
  19. js-ES6学习笔记-async函数(3)
  20. 【bzoj4084】【sdoi2015】双旋转字符串