河中跳房子
【提交】
http://noi.openjudge.cn/ch0111/10/
【描述】
每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点 远 的终点处均有一个岩石。在起点和终点之间，有 个岩石，每个岩石与起点的距离分别为。
在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。
农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多 个岩石。
请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？
【输入】
第一行包含三个整数 ，相邻两个整数之间用单个空格隔开。
接下来 行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。
【输出】
一个整数，最长可能的最短跳跃距离。
【样例输入】
25 5 2
2
11
14
17
21
【样例输出】
4
【提示】
在移除位于2和14的两个岩石之后，最短跳跃距离为4（从17到21或从21到25）。
【参考程序】
问题：长度为 的线段中有 个点，移除 个点，留下 个点，将整条线段划分为 个线段。求所有可能的划分方案中，最短线段最长的那种方案下，最短线段的长度。
如果给定点之间最小距离为 ，即点之间的距离必须 。
需要满足条件为：看移除 个点的多种方案中，是否存在一种方案其最短线段长度。
而要判断该条件是否成立，仍然比较困难。我们可以逆向思考该命题，将其转化为：让每条线段长度都 ，看最少需要移除多少个点。
如果移除的点的数量小于等于，则存在一种方案其最短线段长度，条件成立。 如果移除的点的数量大于，则不存在这样的方案，条件不成立。
清楚要判断的条件后，这就是一个二分答案求满足某一条件最大值的问题。
求中点：mid = (l + r)/2;
如果满足条件，下一次应该更大，取右半边，l = mid + 1; 如果不满足条件，下一次应该更小，取左半边，r = mid - 1;
最后得到的结果就是要求的各种方案中最短线段的最大值。
/*
* 10:河中跳房子
* http://noi.openjudge.cn/ch0111/10/
*/
#include<iostream>
using namespace std;
const int N = 50005;
int arr[N];
int l, n, m;
bool check(int x)
{
int t = 0, num = 0;//t:当前观察的点的位置
for (int i = 1; i <= n; i++)
{
if (arr[i] - t < x)
{
num++;
}
else
{
//如果点i到当前观察的位置的距离大于等于x则i的位置为当前观察的位置
t = arr[i];
}
}
if (l - t < x)
{
//如果终点到观察点距离小于x则移除观察点
num++;
}
//看移除点的数量是否小于等于M
return num <= m;
}
int main()
{
cin >> l >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
int le = 0, ri = l, mid;
while (le + 1 < ri)
{
mid = (le + ri) / 2;
if (check(mid))
{
le = mid;
}
else
{
ri = mid;
}
}
cout << le;
return 0;
}青少年编程竞赛交流
「青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），添加小助手微信，让他邀请大家进入学习群。进群之后大家可以参与定期组织的21天刷题打卡、等级考试测评、教育部白名单比赛辅导以及青少年编程组队竞赛等活动。
