P1095 守望者的逃离
题目描述
恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。
现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意：守望者跑步、闪烁或休息活动均以秒(s)为单位，且每次活动的持续时间为整数秒。距离的单位为米(m)。
输入输出格式
输入格式：
输入文件escape.in仅一行，包括空格隔开的三个非负整数M, S, T。
输出格式：
输出文件escape.out包含两行：
第1行为字符串“Yes”或“No”（区分大小写），即守望者是否能逃离荒岛。
第2行包含一个整数。第一行为“Yes”（区分大小写）时表示守望者逃离荒岛的最短时间；第一行为“No”（区分大小写）时表示守望者能走的最远距离。
输入输出样例
【输入样例1】 39 200 4 【输入样例2】 36 255 10
【输出样例1】 No 197 【输出样例2】 Yes 6
说明
30%的数据满足：1 <= T <= 10, 1 <= S <= 100
50%的数据满足：1 <= T <= 1000, 1 <= S <= 10000
100%的数据满足：1 <= T <= 300000, 0 <= M <= 1000, 1 <= S <= 10^8.
分析：
奔跑速度为每秒钟17米
10点魔法闪现60米
5秒恢复20点魔法 闪现120米 ，就是只用魔法七秒120米
每秒平均17.14米。
用搜索的话，会产生很多重复的运算。
比如先闪现，和先奔跑，还有先奔跑和先闪现是一样的，但是搜索是搜所有情况，这样对于深度足够大的时候，重复的次数就会变得非常的多。
正解：
所以我们只需要一个简单的循环，就可以把搜索模拟出来而且不会出现重复情况。
我们优先一个人只用魔法，然后另外一个人只奔跑。
对于每秒钟留下移动距离最大的人。
因为先闪现和先奔跑时一样的。
因为移动速度是每秒17米 闪烁平均速度是每秒17.14米。
优先闪烁 ，所以一个人只闪烁并不会影响总体结果的最优性。
1 #include <algorithm> 2 #include <iostream> 3 4 using namespace std; 5 6 int m,s,t; 7 int now_s,now_time; 8 int nows,tim; 9 10 int main() 11 { 12 cin>>m>>s>>t; 13 while(now_time<t&&s>now_s) 14 { 15 now_s+=17; 16 if(m>=10) m-=10,nows+=60; 17 else m+=4; 18 now_s=max(now_s,nows); 19 now_time++; 20 } 21 if(now_s<s||now_time>t) cout<<"No"<<endl<<now_s; 22 else cout<<"Yes"<<endl<<now_time; 23 return 0; 24 }