\(AcWing\) \(431\). 守望者的逃离

一、题目描述

恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。

守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。

为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。

到那时，岛上的所有人都会遇难。

守望者的 跑步速度 为 \(17m/s\)，以这样的速度是无法逃离荒岛的。

庆幸的是守望者拥有 闪烁法术，可在 \(1s\) 内移动 \(60m\)，不过每次使用闪烁法术都会 消耗魔法值 \(10\)点。

守望者的魔法值恢复的速度为 \(4\) 点/\(s\)，只有 处在原地休息状态时才能恢复。

现在已知守望者的魔法初值 \(M\)，他所在的初始位置与岛的出口之间的距离 \(S\)，岛沉没的时间 \(T\)。

你的任务是写一个程序帮助守望者计算如何在 最短的时间内 逃离荒岛，若不能逃出，则输出守望
者在剩下的时间能走的最远距离。

注意：守望者跑步、闪烁或休息活动均以秒(\(s\))为单位，且每次活动的持续时间为整数秒。距离的单位为米(\(m\))。

输入格式
输入文件仅一行，包括空格隔开的三个非负整数 \(M,S,T\)。

输出格式
输出文件包括两行：

第 \(1\) 行为字符串 Yes 或 No（区分大小写），即守望者是否能逃离荒岛。

第 \(2\) 行包含一个整数，第一行为 Yes 时表示守望者逃离荒岛的最短时间；第一行为 No 时表示守望者能走的最远距离。

数据范围
\(1≤T≤300000,0≤M≤1000,1≤S≤10^8\)

输入样例：

39 200 4

输出样例：

No
197

输入样例#2：

36 255 10

输出样例#2：

Yes
6

二、解题思路

机房\(dalao\)：一看就是弱智\(dp\)题。然后他切了。但是我因为太菜第一想法是全都进行闪现。下面进行分析。

每次恢复魔力值\(10\)点需要\(2.5s\)，再用\(1s\)进行\(60m\)的闪现，\(60/3.5\)大概是\(17.14m/s\)的速度，刚出发的时候还有一些魔力值。跑步速度是\(17m/s\)，这样看来似乎闪现是最优选，我们愉快的贪心吧！！于是我立马写了个代码交上：

#include <bits/stdc++.h>
using namespace std;
int m; // 初始魔法值
int s; // 他所在的初始位置与岛的出口之间的距离
int t; // 岛沉没的时间
int d; // 守望者在剩下的时间内能走的最远距离

// 贪心思路，可能过 5/11
int main() {
    cin >> m >> s >> t;
    for (int i = 1; i <= t; i++) { // 枚举每一秒
        if (m >= 10) {             // 如果剩余魔法值大于10，那么可以进行闪烁
            m -= 10;               // 魔法值减10
            d += 60;               // 距离增加60
        } else
            m += 4; // 停下来，消耗1秒，魔法值恢复4点

        if (d >= s) {              // 如果走的距离已经大于目标距离，可以走出
            cout << "Yes" << endl; // 说明可以走出去
            cout << i << endl;     // 输出需要几秒
            return 0;
        }
    }
    cout << "No" << endl; // 走不出去
    cout << d << endl;    // 最远可以走到d这个位置上
    return 0;
}

很好，样例都没过。但是我怎么可能这么轻易认输呢，我干脆点了提交。

虽然\(WA\)了一半，但\(A\)了一半说明它并不是全无道理。或许可以推出正确的思路呢？

以样例为例，39 200 4这组数据正确的最远距离结果是\(197\)，这份代码输出的结果则是\(180\).我们可以看出来，最后一秒中本可以跑步\(17m\)，这份代码却会让守望者原地等待。

再看36 255 10这组，正确的最短时间是\(6s\)，这份程序的结果是\(9s\)。我们人工模拟一下，可以发现在\(5s-6s\)时我们可以选择跑步啊！而这个废物代码却会原地等待\(3s\)后再进行闪现。

这时我又觉得我会了！只要判断一下不就好了吗！

#include <bits/stdc++.h>
using namespace std;

int m; // 初始魔法值
int s; // 他所在的初始位置与岛的出口之间的距离
int t; // 岛沉没的时间
int d; // 守望者在剩下的时间内能走的最远距离

int main() {
    cin >> m >> s >> t;
    for (int i = 1; i <= t; i++) { // 枚举每一秒
        if (s - d <= 17) {         // 如果距离小于17，那么可以在1秒内跑步走完，不用再等魔法值恢复
            cout << "Yes" << endl; // 说明可以走出去
            cout << i << endl;     // 输出需要几秒
            return 0;
        }

        if (i == t && m < 10) { // 时间到达最后1秒，还剩下1秒的时间，并且不足以进行一次闪烁
            cout << "No" << endl;
            cout << d + 17 << endl; // 这1秒跑步吧
            return 0;
        }

        if (m >= 10) { // 能闪烁尽量闪烁
            m -= 10;   // 用一次闪烁，魔法值就减少10个
            d += 60;   // 能跑60米
        } else
            m += 4; // 本秒用于回血，1秒可以恢复4个血

        if (d >= s) {
            cout << "Yes" << endl; // 说明可以走出去
            cout << i << endl;     // 输出需要几秒
            return 0;
        }
    }
    cout << "No" << endl; // 走不出去
    cout << d << endl;    // 最远可以走到d这个位置上
    return 0;
}

好，这次看起来好多了，我们再提交一下试试。

只是多\(A\)了一个点，说明优化还是有问题。思考过后我们可以想到，每秒中我们有三种决定：闪现、跑步和停留。停留和闪现可以合并在一起，我们的优化只给了最后一秒跑步的选择。

于是我们可以运用一种似乎很像动态规划的解法啦！我们先假设全部进行闪现-停留-闪现操作，再加一个循环判断每秒的最优决策究竟是闪现-停留还是跑步。我们用\(f[i]\)数组表示第\(i\)秒时守望者 所能到的最远距离。

#include <iostream>
using namespace std;
const int N = 300010;
int m;    // 初始魔法值
int s;    // 他所在的初始位置与岛的出口之间的距离
int t;    // 岛沉没的时间
int f[N]; // f[i]数组表示第i秒时守望者所能到的最远距离

int main() {
    cin >> m >> s >> t;
    for (int i = 1; i <= t; i++) { // 相当于第一次提交的程序
        if (m >= 10) {             // 能闪烁尽量闪烁
            m -= 10;
            f[i] = f[i - 1] + 60; // 最大距离可以增加60米
        } else {
            m += 4;          // 不能闪烁，那么就站在原地回血
            f[i] = f[i - 1]; // 距离没有长大
        }
    }
    // 问题是站在原地回血不一定是最优选择，也可以在此时选择跑步啊~
    for (int i = 1; i <= t; i++) {
        f[i] = max(f[i], f[i - 1] + 17); // 如果在第i秒时跑步能到达更远距离，我们跑步
        if (f[i] >= s) {                 // 已到达就可以输出+结束程序啦
            cout << "Yes" << endl;
            cout << i << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    cout << f[t] << endl; // 如果进行到了这里说明无法逃离，我们输出能到达的最远距离
    return 0;
}

这次的样例也过了，于是我们提交一下。

一道黄题耗我十五分钟我果然还是太菜了

这样就通过了！如果有兴趣的话大家可以研究一下暴力写法，也是能过的（我懒得想了

谨记教训：犹豫就会败北，果断就会白给！！！