ZeroJudge 解題筆記：p900. 旅遊計畫 (Travel)

作者：王一哲
日期：2025年6月17日


ZeroJudge 題目連結：p900. 旅遊計畫 (Travel)

解題想法

完整地掃過 i = 0 ~ 9 天的去程費用，再掃過 j = i ~ 9 的回程費用，更新最低費用。

Python 程式碼

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

import sys

for line in sys.stdin:
    going_trip = tuple(map(int, line .split()))  # 去程費用
    return_trip = tuple(map(int, input().split()))  # 回程費用
    start, end, imin = 0, 0, float('inf')  # 出發日、回程日、最低費用
    for i in range(10):  # 依序掃過 i = 0 ~ 9
        for j in range(i, 10):  # 依序掃過 j = i ~ 9
            fee = going_trip[i] + return_trip[j] + (j-i)*1000  # 費用
            if fee < imin:  # 如果是新的最低費用，更新 start, end, imin
                start, end, imin = i+1, j+1, fee
    print(start, end, imin)

C++ 程式碼

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

#include <cstdio>
using namespace std;

int main () {
    int f;  // 暫存費用的變數
    while(scanf("%d", &f) != EOF) {
        int going_trip[10], return_trip[10];  // 去程費用，回程費用
        going_trip[0] = f;
        for(int i=1; i<10; i++) scanf("%d", &going_trip[i]);
        for(int i=0; i<10; i++) scanf("%d", &return_trip[i]);
        int start = 0, end = 0, imin = 1E9;  // 出發日、回程日、最低費用
        for(int i=0; i<10; i++) {  // 依序掃過 i = 0 ~ 9
            for(int j=i; j<10; j++) {  // 依序掃過 j = i ~ 9
                int fee = going_trip[i] + return_trip[j] + (j-i)*1000;  // 費用
                if (fee < imin) {  // 如果是新的最低費用，更新 start, end, imin
                    start = i+1; end = j+1; imin = fee;
                }
            }
        }
        printf("%d %d %d\n", start, end, imin);
    }
    return 0;
}