题目：跑步17m/s，闪烁60m/s且消耗魔法值10点，处于原地状态魔法值恢复4点/s
输入：魔法初值M，距离S，时间T
输出：是否可以逃出，逃出所花费的最少时间，未逃出所走的最远距离
洛谷大神太牛了，我写了60行的暴力模拟加贪心只有90分，大佬30行就AC完了
思路：很明显闪烁的速度比跑步的速度快很多，但是需要消耗魔法值10点。依据贪心的策略，首先能闪烁就闪烁，不能闪烁之后需要面临两种选择，是继续原地等待等魔法值恢复到大于10点后闪烁还是跑步。在这里我之前用了分类讨论的思想，选择前进的方式和剩下的魔法值有关系，但是这种分类方式很复杂，经过各种WA才90分。看了题解之后大佬提供了一种更简单的方法，让两种方法同时进行，一旦发现闪烁的距离比跑步的距离远就把闪烁的距离赋给跑步的距离。
闪烁和跑步必须是分步进行的不能闪烁-跑步-闪烁，因为贪心意味着每一步都是最佳解决方案，跑步方式前进即说明闪烁方式放弃，魔法值不够用，等待10点积累满加上闪烁时间比一直跑步的距离短，那么无论何时等待魔法值积满闪烁都会比跑步距离短，所以只需要把跑步距离不断用闪烁更新，闪烁距离不用改变。
1 #include<iostream> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 int main() 6 { 7 int M, S, T; 8 cin >> M >> S >> T; 9 int s1 = 0, s2 = 0;//s1跑步，s2闪烁 10 for (int i = 1; i <= T; ++i) 11 { 12 if (M >= 10) { s2 += 60; M -= 10; }//能闪烁就闪烁 13 else { M += 4; }//不能闪烁就恢复魔法值 14 s1 += 17;//s1不断跑步 15 if (s2 > s1)s1 = s2;//闪烁值比跑步值大时，跑步值更新 16 if (s1 > S) { cout << "Yes" << endl << i << endl; system("pause"); return 0; }//跑出去了就结束程序 17 } 18 cout << "No" << endl << s1 << endl;//没跑出去输出S1 19 system("pause"); 20 return 0; 21 }
原文：https://www.cnblogs.com/xiongyuqing/p/12240439.html