2016华为校招上机试题2——洞穴逃生

二、洞穴逃生
描述：精灵王子爱好冒险，在一次探险历程中，他进入了一个神秘的山洞。在洞穴深处，精灵王子不小心触动了洞穴内暗藏的机关，整个洞穴将很快塌陷，精灵王子必须尽快逃离洞穴。精灵王子的跑步速度为17m/s，以这样的速度可能是无法逃出洞穴的。庆幸的是精灵王子拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。精灵王子的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。现在已知精灵王子的魔法初值M，他所在洞穴中的位置与洞穴出口之间的距离S，距离洞穴塌陷的时间T。你的任务是写一个程序帮助精灵王子计算如何在最短的时间内逃离洞穴。若能逃出，输出”Yes”，并输出逃出所用的最短时间；若不能逃出，则输出”No”，同时输出精灵王子在剩下的时间内能走的最远距离。注意字母大小写。
注意：精灵王子跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。 注：M、S、T均是大于等于0的整数。由输入保证取值合法性，考生不用检查。
提醒： 如果输入的S为0，则说明本身已经在出口，输出应为：Yes 0
如果输入的T为0（且S不为0），则说明已经没有时间了，输出应为：No 0
输入: M S T
输出: “Yes 逃出洞穴所用的最短时间” 或 “No 在洞穴塌陷前能逃跑的最远距离”
样例输入: 10 50 5
样例输出：Yes 1

题目分析：首先看题目中给出的两种王子逃跑的方式——跑步和魔法。跑步的速度是17m/s，使用闪烁法术的移动速度是60m/s，可见魔法足够时使用魔法是最优的方式。当魔法不够时，就要权衡是花时间恢复魔法还是跑步，权衡依赖的两个因素是距离洞口的距离和剩余时间，剩余时间要足够恢复和使用魔法，且距离洞口要足够远（比如如果距离洞口仅仅1m直接跑出去就好了，不用浪费时间恢复魔法），因此，有如下几种情况：
1）魔法值足够且时间不为0的情况下，不论距离多远，直接魔法闪烁；
2）若剩余魔法值大于等于6，则只需要1s就可恢复到10点魔法，此时若时间大于2秒（因为释放魔法需要1s），且距离洞口距离大于34m（若小于34m直接花2s跑出去就好了），恢复魔法然后闪烁；
3）若剩余魔法值大于等于2，则只需要2s就可恢复到10点魔法，此时若时间大于3秒，且距离洞口距离大于51m，恢复魔法然后闪烁；
4）第四种情况比较复杂，若魔法剩余小于2，则恢复魔法要3s，施放魔法要1s，这种情况还比不上跑步来得快，但是如果后面的距离还足够长，且时间足够的话，那么接下来那一次只需要2s来恢复魔法，这样（3+1）+（2+1）=7s内可以移动120m，比跑步快，因此当距离大于120m，时间大于7s时，选择恢复魔法后闪烁；
5）如果不满足以上四种条件，表明时间不够恢复魔法或者是距离较近，则选择跑步前进。

程序代码：

#include <iostream>
using namespace std;
int main()
{
    int S,T,M;

    cin>>M>>S>>T;

    int s0 = S,t0 = T,m0 = M;

    if(S<=0)//本身已在出口之外
    {
        cout<<"Yes "<<0;
        return 0;
    }
    else if(T<=0)//没有时间了
    {
        cout<<"No "<<0;
        return 0;
    }

    while(S>0 && T>0)
    {
        if( M>=10)//魔法足够时——使用魔法
        {
            T--;
            M = M - 10;
            S = S - 60;
            continue;
        }
        else if( M>=2 && T-ceil(float((10-M))/4)>=1 && S-17*ceil(float((10-M))/4)>=0 )//如果M>=2，并且距离够远、时间足够——恢复魔法
        {
            int t = ceil(float((10-M))/4);
            T = T - t;
            M = M + 4*t;
            continue;
        }
        else if( S>=120 && T>=7)//如果M<2，并且距离大于等于120m、时间大于等于7s——恢复魔法
        {
            T = T - 3;
            M = M + 12;
            continue;
        }
        else//魔法不够、时间也不够，或者距离洞口很近的情况下
        {
            S = S - 17;
            T--;
        }
    }

    if(S<=0)
    {
        cout<<"Yes "<<t0-T;
    }
    else
    {
        cout<<"N0 "<<s0-S;
    }

    return 0;
}

注：代码中将第2种和第3种情况合并了。另外一定要注意while循环的出口条件，时间和距离一旦有一个小于等于0，就要停止。以下附上几组测试用例
10 0 0
Yes 0

10 1 0
No 0

3 50 3
Yes 3

1 60 4
Yes 4

1 77 4
No 68

3 77 4
Yes 4

1 120 8
Yes 7

1 137 8
Yes 8

1 147 8
No 137