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元起，快前往官网查看详情吧