守望者的逃离问题是算法中一个很经典的案例,特别是在贪心算法中经常会被引用。今天我们就来总结一下这个问题的多种解法。

题目

恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去。到那时,岛上的所有人都会遇难。守望者的跑步速度为17m/s,以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术,可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s,只有处在原地休息状态时才能恢复。
现在已知:
守望者的魔法初值start_magic;
他所在的初始位置与岛的出口之间的距离total_dist;
岛沉没的时间sink_time;

你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛:

  • 若逃出,输出Yes及逃跑所用最短时间
  • 若不能逃出,输出No及守望者在剩下的时间内能走的最远距离

注意:守望者跑步、闪烁或休息活动均以秒(s)为单位,且每次活动的持续时间为整数秒。距离的单位为米(m)。

 第一种解法

分析

首先我们简单分析一下跑步和闪烁哪一个快。我们分两种极端情况考虑:只跑步和只闪烁。

只闪烁的情况下,当魔法为0的时候,至少需要3秒(3*4=12点魔法值>10)才可以闪烁一次,再加上闪烁的一秒,则4s内可以移动60m(即闪烁一次的距离)。而如果4s内只跑步,则可以移动4*17=68m。显然,如果这样的话闪烁会比移动慢。但是如果可以休息5s,有4*20点魔法,可以闪烁两次,这样5+2=7s内可以移动60*2=120m;如果7s内只跑步的话,可以移动7+17=119m。可见,如果时间够这样两次两次闪烁的话,闪烁是比跑步快的。所以,我们采用贪心算法:能闪烁就闪烁。这样,就会存在一个问题:在边界的时候(最后一次的时候),可能出现守望者魔法刚回复满,还没来得急闪烁,岛就沉没了,这种情况下,其实他最后一次就不应该等待魔法回复,而应该直接跑步。

综合闪烁会比较快和最后的临界问题两种分析,我们引入两个人,这两个人有如下特点:

  • 两人同时开始逃跑,不过一个人只跑步,一个人只闪烁
  • 如果闪烁的人移动到了跑步的人的前面,就让只跑步的人直接从和只闪烁的人同样的位置开始继续跑步。每秒就进行一次这样的判断,如果只闪烁的人移动的总距离大于只跑步的人的总距离,那么就将只闪烁的人总距离赋给只跑步的人。——这样,是为了解决上面的那个临界问题。具体解释见后面。
  • 每一秒,都要判断是否已经逃离荒岛。因为如果逃离荒岛,就不必再算移动的最大距离了(题目要求只有在未能逃离荒岛时才计算移动的最大距离)。
  • 最后时间到了以后,如果未逃离荒岛,则比较只跑步和只闪烁的人的移动距离,两者取较大值就是可以移动的最大距离。

解释,为什么上面的第二条可以解决临界问题?

总体而言,如果有时间可以闪烁,那么闪烁肯定会比跑步快。而这里我们假设的那个只跑步,其实并不是只跑步,因为当闪烁的人移动的距离比他远的时候,他就可以直接跳到闪烁的人的移动距离那里继续跑步,相当于如果有时间闪烁的话,那么这个“只跑步”的人其实也在闪烁。他唯一和只闪烁的人不同的地方就在于最后的临界情况,假如只闪烁的人最后一次闪烁后移动了P m,只跑步的人移动了Q m,且P>Q,而此时距岛沉没只剩2s了。那么接下来,只跑步和只闪烁的人都从P m开始继续移动,此时对于只跑步的人而言,2s过后,他移动的总距离为P+17*2,而只闪烁的人因为最后2s是要回复魔法的,不会移动,所以2s后他移动的最大距离为P m,显然小于“只跑步”的人。而那个“只跑步”的人最终移动的最大距离也是最大可以移动的距离。要理解这里的关键是要理解这个“只跑步”的人的含义。当然,我们也可以只用一个人,然后每次闪烁完后根据当前魔法值(不够一次闪烁了,如果够,则直接闪烁,无需决定闪烁还是跑步)和剩余时间决定接下来是跑步还是等待回复魔法闪烁,但是这样的效率会比模拟两个人的效率低。这种情况我们在后面的解法中会讨论。

程序

下面的程序,是上述思想的一种实现:

#include <stdio.h>
#include <stdlib.h>

const unsigned int run_speed = 17;
const unsigned int blink_speed = 60;
const unsigned int magic_cost = 10;
const unsigned int magic_recover = 4;

static unsigned int run_total_dist, blink_total_dist;


void Escape(
	unsigned int *p_start_magic,  	//初始魔法
	unsigned int *p_total_dist,		//初始位置距岛出口距离
	unsigned int *p_sink_time		//岛沉默时间
			)
{
	unsigned int sink_time = *p_sink_time;
	unsigned int magic = *p_start_magic;
	unsigned int total_dist = *p_total_dist;

	int sec_use = 1;
	while ( sec_use <= sink_time)
	{
		// 只跑步的人
		run_total_dist += run_speed;

		// 只闪烁的人
		if ( magic < magic_cost )
		{ //不够一次闪烁,则回复魔法
			magic += magic_recover;
		}
		else
		{
			blink_total_dist += blink_speed;
			magic -= magic_cost;
		}

		if ( run_total_dist < blink_total_dist)
		{ //让只跑步的人和只闪烁的人回到同一起跑线
			run_total_dist = blink_total_dist;
		}

		// 注意这里使用run_total_dist和total_dist比较,而不是blink_total_dist
		if ( run_total_dist >= total_dist)
		{
			break;
		}

		sec_use++;
	}

	if (sec_use <= sink_time )
		printf("Yes: %dn", sec_use);
	else
		printf("No: %dn", run_total_dist);

	return;
}

int main()
{
	unsigned int start_magic, total_dist, sink_time;
	printf("请输入初始魔法值:");
	scanf("%d", &start_magic);
	printf("请输入初始位置距岛出口距离: ");
	scanf("%d", &total_dist);
	printf("请输入岛沉默时间: ");
	scanf("%d", &sink_time);

	Escape(&start_magic, &total_dist, &sink_time);

	return 0;
}

 第二种解法(Pending)