[NOIP2007 普及组] 守望者的逃离

dog_emperor · 2023-12-27 20:38:14 · 题解

题目传送门

思路

这道题我们可以用到贪心的思路。

首先，我们有以下三种操作：

• 闪现，耗费 10 点魔，闪 60m，方便讲解说成操作 a。

• 回魔，加上 4 点魔，说成操作 b。

• 跑步，跑 17m，说成操作 c。

当我们的魔为 0 时，见如下操作序列：

由此可知，我们同样为 7s 的操作，回魔闪现跑的是远一点的，而光去跑步会慢一点。所以我们的跑步的次数是不可能会大于或等于 7 的，不然就不是最优解。

为什么呢？因为我们与其去把一个长度大于或等于 7 的序列全用来跑步，不如替换成回魔闪现，这样能跑得更远。

现在我们就可以枚举 0 到 6 来看跑了多少次步。

对于每次枚举，我们可以最开始就把该跑的次数跑完，这样就不影响结果。剩下再来考虑闪现和回魔。

接下来就是一个很好想的贪心，如果我们的魔是大于等于 10 的，就闪现，否则就回魔。

时间复杂度为 O(T) 不会超时（因为枚举跑步次数的时间复杂度是个常数就不计了）。

Code:

#include <bits/stdc++.h>

using namespace std;

int m, s, t, ans;

bool ok;

int main(){
    scanf("%d%d%d", &m, &s, &t);
    for (int z = 0; z <= 6; z++) {
        int mp = m, l = 0;
        for (int i = 1; i <= t; i++) {
            if (i <= z)
                l += 17;
            else {
                if (mp >= 10) 
                    mp -= 10, l += 60;
                else
                    mp += 4;
            } if (l >= s) {
                if (!ok)
                    ok = true, ans = i;
                else
                    ans = min(ans, i);
                break;
            }
        }
        if (l < s && !ok)
            ans = max(ans, l);
    }
    if (ok) 
        printf("Yes\n");
    else
        printf("No\n");
    printf("%d\n", ans);
}