2014华为编程大赛 洞穴逃生 C语言实现

2014华为编程大赛 洞穴逃生 C语言实现

洞穴逃生
描述: 
精灵王子爱好冒险，在一次探险历程中，他进入了一个神秘的山洞。在洞穴深处，精灵王子不小心触动了洞穴内暗藏的机关，整个洞穴将很快塌陷，精灵王子必须尽快逃离洞穴。精灵王子的跑步速度为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

          看到这个题，首先便想到用贪心的思想去解决，即找出在给定条件下，最快的奔跑方式。有了思想，可以得出以下的贪心原则（先考虑在时间充足的情况下，能够最快跑出去的策略）：

      1、由于不考虑小数（即哪怕总距离只有10m，也认为需要奔跑1s），显然，如果初始魔法值是大于等于10，最快方式是消耗10点魔法值来前进60m。

        2、如果魔法值m小于10且大于等于2，那么最多只需2秒就可以回复魔法值到10以上，然后用一次魔法，耗时2s（当m >= 6）或3s(当2<= m <= 6)可以位移60m；如果奔跑的话，3秒只能跑51m。因此在这种情况下，也应该先等到魔法值回复到10以上，用一次魔法。当然这里考虑的是距离大于51m的情况下，如果距离小于等于51m，采用哪种方法更快还需要根据距离和时间的不同取值进行细分的（详见代码），这里主要是根据魔法值介绍贪心原则。

       3、魔法值等于1，或者0。这时，魔法值回复到10以上需要等3s，使用魔法耗费1s，这样4s内可以前进60m；而如果奔跑的话，4s内可以跑68m。可能会有朋友认为此时，采用奔跑的方式会比用魔法更快。但是让我们来看看，假设初使魔法值为0，等3s之后，魔法值回复到了12，使用一次魔法，前进了60m，还剩下2个魔法。这时就回到了第二中情况，再等2s让魔法值就回复到10，再用一次魔法前进60m。这样，用两次魔法一共花了7s，前进了120m，而如果用奔跑的方式，7s只能跑 7*17 = 119m。因此魔法值为1或者0的情况下，如果距离大于120m，应该采用两次魔法的方式，如果距离小于120m，则采用奔跑的方式更快。

         上面根据魔法值的分类，对各种情况下的贪心原则做了介绍（实际上还需要考虑距离和时间对策略的影响）。从上面的结构我们可以看出，对魔法值大于10的复杂情况，我们可以对其用数次魔法之后化简到魔法小于等于10的简单情况，对复杂情况逐步化简，直到化简成为可以直观用分类解决的小问题。对于这种问题，采用递归无疑是最好的解决方案，由于有魔法值，距离，时间三个自变量的约束，分类比较多，但分的大类就是上面介绍的三种情况，C语言代码如下：

#include<stdio.h>/*m,s,t分别代表初始魔法值、距离、时间*psT和*pDist用作传出参数，*pDist用来返回最远能跑的距离，如果能够跑出来则它一定大于等于s。如果能够跑出来，*psT返回跑出来的最短时间*/
void Escape(int m, int s, int t,int *psT,int *pDist)
{if(t <= 0 && s > 0){*pDist = 0;return ;}if(s <= 0){*psT = 0;return ;}int sT1 = 0,sT2 = 0,Dist1 = 0,Dist2 = 0;if(m >= 10 && s > 60){*psT = 1;*pDist = 60;Escape(m - 10, t - 1, s - 60,&sT1,&Dist1);}if(m >= 10 && s <= 60){*psT = 1;*pDist = s;}/*这里是最基本的情况，但里面有几种情况，需要细分*/if(m < 10 && s <= 60){int RecoverT;  //魔法恢复到10以上的时间if(m < 2)RecoverT = 1000000;if(m >= 2 && m < 6)RecoverT = 2;if(m >= 6 && m <= 9)RecoverT = 1;if(t * 17 >= s || RecoverT + 1 <= t)  //满足这一条件则能够逃出去{*pDist = s;if(s <= 17)*psT = 1;else if(s > 17 && s <= 34)*psT = 2;else if(s > 34 && s <= 51){if(RecoverT == 1)*psT = 2;else*psT = 3;}else if(s >= 51){if(RecoverT > 10)*psT = 4;else*psT = RecoverT + 1;}}else    //如果逃不出去，只需算pdist，{*pDist = t * 17;}}if(m < 10 && s > 60){if(m <= 1){if(s >= 120) //只要距离大于120m，则前120m用两次魔法是最快的（7s){            //如果用奔跑则7s只能跑119mif(t >= 7)    //有足够时间用两次魔法，有机会逃出去，可以化简到其它情况{*psT = 7;*pDist = 120;Escape(m , s - 120, t - 7,&sT2,&Dist2);}else  //t < 7,一定逃不出去了{*pDist = 17 * t;}}else //小于120m,那么采用奔跑更快，可以递归到简单情况{*psT = 1;*pDist = 17;Escape(m, s - 17,t - 1,&sT2,&Dist2);}}else if(m >= 2 && m < 6)  //只需两秒可以有超过十个魔力，用魔法3s可以跑60m，因此用掉魔法再说{if(t >= 3)        //有机会用一次魔法，并且可以递归到其它情况{*pDist = 60;*psT = 3;Escape(m - 2, s - 60, t - 3,&sT2,&Dist2);}else //(t < 3)   跑不出去，用不了魔法，只需计算最远能跑的距离{*pDist = 17 * t;}}else // m >= 6{if(t >= 2) //有机会用一次魔法，可以递归到其它情况{*pDist = 60;*psT = 2;Escape(m - 6, s - 60, t - 2,&sT2,&Dist2);}else              //没机会用魔法，逃不出去，只需计算最远能跑的距离{*pDist = t * 17;}}}*psT = *psT + sT1 + sT2 ;   //将每个阶段所花的时间加起来*pDist = *pDist + Dist1 + Dist2; //每个阶段跑的距离加起来}int main()
{int s,t,m;int sT = 0,Dist = 0;scanf("%d %d %d",&m,&s,&t);Escape(m,s,t,&sT,&Dist);if(Dist < s)printf("No %d",Dist);elseprintf("Yes %d",sT);return 0;
}

    以上的代码分类较为详细，所以代码量也较大，应该没有遗漏该有的逻辑，如果有，望不吝指出，万分感谢。