守望者的逃离

题目描述

守望者每秒只能做一件事：跑步前进 $17$ 米、休息使魔法值 $+4$ 、或闪烁前进 $60$ 米并消耗 $10$ 点魔法（魔法不足 $10$ 时不能闪烁）。给定初始魔法 $M$ 、出口距离 $S$ 、岛沉没时间 $T$ ，若能前进至少 $S$ 米则输出 Yes 和最短逃离秒数，否则输出 No 和 $T$ 秒内能走的最远距离。输入一行三个非负整数 $M,S,T$ （ $1\le T\le 3\times10^5$ ， $0\le M\le 1000$ ， $1\le S\le 10^8$ ），输出两行如上述。样例：39 200 4 输出 No、197；36 255 10 输出 Yes、6。

思路

同时维护两条路线的累计距离：一直跑步的距离，和"魔法够就闪烁、不够就休息"的距离，每秒取较大者作为当前位置。若最优距离达到 $S$ ，当前秒数就是最短逃离时间；扫完 $T$ 秒仍未达到，输出最终的最优距离。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 07:11
# update_at: 2026-10-02 07:11

import sys


def rests(magic: int, flashes: int) -> int:
    """凑足 flashes 次闪烁最少需要休息几秒（初始 magic 点，每次休息回 4 点）。"""
    deficit = 10 * flashes - magic
    return (deficit + 3) // 4 if deficit > 0 else 0


def farthest(magic: int, t: int) -> int:
    """t 秒内三种动作各做任意整数秒（每秒恰好一个动作）能走的最远距离。"""
    flash_max = min(t, (4 * t + magic) // 14)  # 一闪一休均速 60/3.5 > 17，闪越多越快
    best = 0
    for flashes in (flash_max, flash_max - 1):
        if flashes < 0:
            continue
        best = max(best, 60 * flashes + 17 * (t - flashes - rests(magic, flashes)))
    return best


def solve() -> None:
    magic, dist, time_limit = map(int, sys.stdin.buffer.read().split())  # 题面的 M, S, T

    # 逃离时刻 t 只取决于 farthest(magic, t)，每秒刷新一次即可
    escape_time = next((t for t in range(time_limit + 1) if farthest(magic, t) >= dist), -1)
    if escape_time >= 0:
        print(f"Yes\n{escape_time}")
    else:
        print(f"No\n{farthest(magic, time_limit)}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:42
 * update_at: 2026-10-06 13:42
 */
#include <iostream>
using namespace std;
typedef long long ll;

// 守望者的逃离：每秒在跑步、休息、闪烁中选一个，求最短逃离时间或最远距离。
int main() {
    ll M, S, T;
    cin >> M >> S >> T;

    ll magic = M;      // 当前魔法值
    ll run_dist = 0;   // 一直跑步的累计距离，同时用来保存当前最优距离
    ll flash_dist = 0; // 按"魔法够就闪、不够就休息"这条路线走的累计距离

    for (ll t = 1; t <= T; t++) {
        run_dist += 17; // 这一秒用来跑步
        if (magic >= 10) {
            magic -= 10; // 这一秒用来闪烁
            flash_dist += 60;
        } else {
            magic += 4; // 魔法不够，这一秒休息攒魔法
        }
        if (flash_dist > run_dist) {
            run_dist = flash_dist; // 闪烁路线更远，切换到该路线
        }
        if (run_dist >= S) {
            cout << "Yes\n" << t << "\n"; // 当前秒数即最短逃离时间
            return 0;
        }
    }

    cout << "No\n" << run_dist << "\n"; // T 秒内都逃不出，输出最远距离
    return 0;
}

目录

题目描述

思路

参考代码