【Vijos】1431 守望者的逃离

题目链接：https://vijos.org/p/1431

算法：贪心

 

这道题刚开始看到tag以为是背包，然后就想怎么做，一直想不出来，发现设状态不行。。。

然后慢慢觉得可以贪心，于是就用贪心写了。但写完后发现自己的贪心策略错了。。。。。看题解。

！巧妙！

我们可以假设两个人a和b在同时跑，a用+17的跑法；b一直用魔法，魔法用完了就休息。

然后是比较，如果在同一时间完后，a的路程小于b，那么就把b的路程赋给a。（贪心）

为什么当a>b的时候不用将a赋值给b？1. b已经休息过了 2.即使b不休息，当a>b时，赋值给b也就相当于a自己走了17一样，无意义。用魔法的总量是一定的，在哪用都一样，所以可以不用更新b的+17

代码：

#include <cstdio>

using namespace std;

int m, s, t, i, ans1, ans2;

int main() {

	scanf("%d%d%d", &m, &s, &t);

	for(i = 1; i <= t; ++i) {

		ans1 += 17;

		if(m >= 10) ans2 += 60, m -= 10;

		else m += 4;

		if(ans1 < ans2) ans1 = ans2;

		if(ans1 >= s) break;

	}

	if(ans1 >= s) printf("Yes\n%d\n", i);

	else printf("No\n%d\n", ans1);

	return 0;

}