ZeroJudge 解題筆記：f820. 極限運動 (Sports)

作者：王一哲
日期：2025年3月20日



ZeroJudge 題目連結：f820. 極限運動 (Sports)

解題想法

這題在左、右兩側各加上超出題目範圍的極大值，在向左、右找終點時可以避免出界。

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # 地圖上有 n 個位置
    hs = [1000] + list(map(int, input().split())) + [1000]  # 各位置高度，兩端加上 1000
    s = int(input())  # 起點 s
    e = s  # 終點 e 設定為 s
    if s == 1:  # 只能往右滑
        while hs[e] >= hs[e+1]: e += 1  # 向右滑直到右側高度大於左側為止
    elif s == n:  # 只能往左滑
        while hs[e] >= hs[e-1]: e -= 1  # 向左滑直到左側高度大於右側為止
    else:  # 可以向左或向右滑
        if hs[e-1] < hs[e+1]:  # 左側較低，向左滑
            while hs[e] >= hs[e-1]: e -= 1  # 向左滑直到左側高度大於右側為止
        else:  # 右側較低，向右滑
            while hs[e] >= hs[e+1]: e += 1  # 向右滑直到右側高度大於左側為止
    print(e)  # 印出終點

C++ 程式碼

使用時間約為 2 ms，記憶體約為 336 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 地圖上有 n 個位置
    while(cin >> n) {
        int hs[n+2];  // 各位置高度，兩端加上 1000
        hs[0] = hs[n+1] = 1000;
        for(int i=1; i<=n; i++) cin >> hs[i];
        int s, e; cin >> s;  // 起點 s，終點 e
        e = s;  // e 設定為 s
        if (s == 1) {  // 只能往右滑
            while(hs[e] >= hs[e+1]) e++;  // 向右滑直到右側高度大於左側為止
        } else if (s == n) {  // 只能往左滑
            while(hs[e] >= hs[e-1]) e--;  // 向左滑直到左側高度大於右側為止
        } else {  // 可以向左或向右滑
            if (hs[e-1] < hs[e+1]) {  // 左側較低，向左滑
                while(hs[e] >= hs[e-1]) e--;  // 向左滑直到左側高度大於右側為止
            } else {  // 右側較低，向右滑
                while(hs[e] >= hs[e+1]) e++;  // 向右滑直到右側高度大於左側為止
            }
        }
        cout << e << "\n";  // 印出終點
    }
    return 0;
}