P2678[NOIP2015提高组]跳石头题解-创新互联
用于个人学习记录
一、题目描述
二、方法介绍
二分查找——在有序数组中折半查找所需值（默认数组升序）
- 初始将整个数组作为查找区域 记数组最左侧下标为 left 数组最右侧下标为 right 查找区域[left, right]
- 将查找区域的中间值与所需值进行比较，若大于所需值，则此时右半侧区间内的值均大于所需值（数组升序排列从左到右数字大小依次增大），舍弃右侧区间，在左侧区间内继续查找。若小于所需值，则此时左半侧区间内的值均小于所需值，舍弃左区间，在右侧区间继续查找。
- 直至此时的中间值等于所需值，则输出。或已经没有可以继续查找的区间但仍未找到所需值。
代码实现
#includeint main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//数组需为有序数组
int k = 7;//k为所需值
int sz = sizeof(arr) / sizeof(arr[0]);//数组总大小/每个数的大小=数的个数
int left = 0;
int right = sz - 1;//想知道right的值必须先知道数组中数的个数
while (left<= right)//当left >right则表明已没有可继续查找的区间
{//通过比较区间中间数与k的大小一步步缩短区间最终找到k
//int mid = (right + left) / 2;//这种方法求mid有弊端，如果left + right超出int的范围则会影响mid的值
int mid = left + (right - left) / 2;
if (arr[mid] >k) {
right = mid - 1;//舍弃右侧区间
}
else if (arr[mid]< k) {
left = mid + 1;//舍弃左侧区间
}
else if (arr[mid] == k){
printf("下标为：%d", mid);//此时返回的为数在数组中的下标
break;//找到所需值时即可终止
}
}
if (left >right)
{
printf("false");//代表未能在数组中找到所需值
}
return 0;
} 三、题解
- 题意分析
最短跳跃距离的大值（说实话我一开始半天没读懂，语文不好真的会对题目这种说法疑惑，不过可能只有我没看懂）
以题目样例为例
一开始的石头分别位于2 11 14 17 21
则相邻两块石头的距离分别为 2，9，3，3，4，4(包括第一块与起始位置的距离，最后一块与终点的距离)此时最短跳跃距离为2
移去距离为2和14的两块石头后，相邻两块石头间距离分别为11，6，4，4则最短跳跃距离为4
假设移走的为距离为2和17的，那么相邻两块石头间距离分别为11，3，7，4则最短跳跃距离为3，小于4。同样可以假设移走另外两块石头，会发现得出的最短跳跃距离均小于4，所以4为最短跳跃距离的大值。
- 真正的题解
抛开一切其他条件时最短跳跃距离大可为起始点与终点距离(总距离)的一半，所以可将总距离视为一个升序数组，从一到总距离均为可能的解的值，用二分法查找符合条件的大的解能为多少，判断条件即为要使最短跳跃距离为这个值，需要移走的石头数量是否符合条件。
代码实现
#define _CRT_SECURE_NO_WARNINGS
#includeint L = 0, N = 0, M = 0;//起点和终点的距离(总距离)，岩石数量,移走的岩石的数量
int n[50002] = { 0 };//记录每块石头与起点的距离
int judge(int x) {//判断此时的解是否符合要求(搬走的石头的数量不超过M)
int count = 0;//记录在最短距离为x的情况下需要搬走的石头的数量
int now = 0, to = 1;//现在的位置和要去的位置
while (to<= N + 1) {//最后一块石头跳到终点的距离也要判断
if (n[to] - n[now]< x) {//此时这两块石头之间的距离没有达到假设的最小距离
count++;//搬走这块石头使此时所在石头与下一块石头之间的距离增大
}
else {//此时所在石头与下一块石头间的距离符合假设的值不需要搬走石头，直接跳过去，所以更新此时所在的位置
now = to;
}
to++;
}
if (count >M)
return 0;
else
return 1;
}
//主函数
int main()
{
scanf("%d %d %d", &L, &N, &M);
n[0] = 0, n[N + 1] = L;//记录起始点和终点
for (int i = 1; i<= N; i++) {
scanf("%d", &n[i]);
}
int left = 0, right = L;//从大的可能开始逐个排除(一步登天)
int mlen = 0;//记录结果
while (left<= right) {
int mid = (left + right) / 2;
if (judge(mid) == 1) {//如果此时的mid符合要求(一般都不会是大值<是大好像也不影响>,所以要判断是否有更大的可行值)
mlen = mid;//先记录一下此时的答案
left = mid + 1;//判断是否有更大的可行值
}
else {//最小距离的大值不能达到mid,减小这个值
right = mid - 1;
}
}
printf("%d", mlen);
return 0;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享名称：P2678[NOIP2015提高组]跳石头题解-创新互联
网页地址：http://cdiso.cn/article/jjcgi.html
