ZeroJudge 解題筆記：k925. P2. 海底探險 (Adventure)

作者：王一哲
日期：2025年5月15日



ZeroJudge 題目連結：k925. P2. 海底探險 (Adventure)

解題想法

這題我沒有想到比較簡潔的寫法，只能按照題目的敘述模擬烏龜的運動過程，程式碼寫起來很長。

Python 程式碼

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

import sys

def solve(L, T, hs):
    rem = T-1  # 剩下的探索時間，先減 1
    hmax = max(hs)  # 最高區塊高度
    imax = hs.index(hmax)  # 最高區塊位置
    t1 = hmax - hs[0]  # 上升到最高區塊高度需要的時間
    rem -= t1  # 更新 rem
    if rem <= 0: return 1  # 已經用完探索時間，還在起點區塊，回傳 1
    t2 = imax  # 向右游到最高區塊需要的時間
    rem -= t2  # 更新 rem
    if rem <= 0: return T-t1  # 向右游到的區塊 T-1-t1+1
    if imax == L-1:  # 如果游到最右邊
        hmin = min(hs[1:L-1])  # hs[1] ~ hs[L-2] 最低點
        imin = L-2 - hs[1:L-1][::-1].index(hmin)  # hs[1] ~ hs[L-2] 最低點位置
        t3 = L-1-imin  # 向左游到 imin 需要的時間
        rem -= t3  # 更新 rem
        if rem <= 0: return L-(rem+t3)  # 游到區塊 2 前時間就到了
        return imin + 1  # 可以游到區塊 imin + 1
    else:  # 不是游到最右邊
        hmax2 = max(hs[imax+1:])  # imax 右側最高的區塊高度
        imax2 = hs[imax+1:].index(hmax2) + imax + 1  # hmax2 的位置
        t3 = imax2-imax  # 向右游到 imin2 需要的時間
        rem -= t3  # 更新 rem
        if rem <= 0: return imax+rem+t3+1  # 游到 imax2 + 1 前時間就到了
        return imax2 + 1  # 可以游到 imax2 + 1

for line in sys.stdin:
    L = int(line)  # L 個區塊
    hs = list(map(int, input().split()))  # 各區塊高度
    T = int(input())  # 探索時間
    print(solve(L, T, hs))

C++ 程式碼

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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int solve(int L, int T, vector<int>& hs) {
    int rem = T-1;  // 剩下的探索時間，先減 1
    auto it = max_element(hs.begin(), hs.end());  // 最高區塊高度
    int hmax = *it, imax = it - hs.begin();  // 最高區塊位置
    int t1 = hmax - hs[0];  // 上升到最高區塊高度需要的時間
    rem -= t1;  // 更新 rem
    if (rem <= 0) return 1;  // 已經用完探索時間，還在起點區塊，回傳 1
    int t2 = imax;  // 向右游到最高區塊需要的時間
    rem -= t2;  // 更新 rem
    if (rem <= 0) return T-t1;  // 向右游到的區塊 T-1-t1+1
    if (imax == L-1) {  // 如果游到最右邊
        int hmin = hs[L-2], imin = L-2;  // hs[1] ~ hs[L-2] 最低點高度及位置，先訂成 hs[L-2]，再向左線性搜尋
        for(int i=L-3; i>=1; i--) {
            if (hs[i] < hmin) {
                hmin = hs[i]; imin = i;
            }
        }
        int t3 = L-1-imin;  // 向左游到 imin 需要的時間
        rem -= t3;  // 更新 rem
        if (rem <= 0) return L-(rem+t3);  // 游到區塊 2 前時間就到了
        return imin + 1;  // 可以游到區塊 imin + 1
    } else {  // 不是游到最右邊
        auto it2 = max_element(hs.begin()+imax+1, hs.end());  // imax 右側最高的區塊高度
        int imax2 = it2 - hs.begin();  // hmax2 的值及位置
        int t3 = imax2-imax;  // 向右游到 imin2 需要的時間
        rem -= t3;  // 更新 rem
        if (rem <= 0) return imax+rem+t3+1;  // 游到 imax2 + 1 前時間就到了
        return imax2 + 1;  // 可以游到 imax2 + 1
    }
}

int main() {
    int L;  // L 個區塊
    while(scanf("%d", &L) != EOF) {
        vector<int> hs (L);  // 各區塊高度
        for(int i=0; i<L; i++) scanf("%d", &hs[i]);
        int T; scanf("%d", &T);  // 探索時間
        printf("%d\n", solve(L, T, hs));
    }
    return 0;
}