置頂

我的 VPython 教學文件 (HackMD 版本)

VPython 教學文件目錄 安裝及測試 基本語法 等速度直線運動 自由落下 終端速度 水平抛射 使用For迴圈計算水平抛射資料 斜向抛射 圓周運動 簡諧運動 單擺 木塊彈簧系統分離 重力及簡諧 行星運動 相疊木塊 雙重簡諧運動 一維彈性碰撞 ...

熱門文章

2026年11月18日 星期三

ZeroJudge 解題筆記:e664.108 p2. 空氣盒子

作者:王一哲
日期:2026年11月18日


ZeroJudge 題目連結:e664.108 p2. 空氣盒子

解題想法


先將不確定筆數的測資存入陣列 $arr$ 之中,為了配合天數從 $1$ 開始計算,$arr$ 開頭多加一個 $0$。預設目前讀到的極小值 $imin = arr[1]$、極大值 $imax = arr[1]$,峰值開始日期為 $start = 0$,峰值結束日期後一天為 $end = 0$,布林值 has_peak 記錄是否有峰值。接下來用一個 for 迴圈讀取 $i = 2$ 到 $i = n-2$ 天的數值,如果 $arr[i] > arr[i-1]$ 可能有新的峰值,記錄 $imax = arr[i], start = i$;如果 $arr[i] < arr[i-1]$ 可能結束一個峰值,記錄 $imin = arr[i], end = i$;如果 $start \neq 0, end \neq 0, start < end, imax > imin$,則 $start$ 到 $end - 1$ 天之間為峰值。

Python 程式碼


使用時間約為 12 ms,記憶體約為 9.5 MB,通過測試。
while True:
    try:
        arr = [0] + list(map(int, input().split()))
    except EOFError:
        break
    
    n = len(arr)  # 天數加 1
    imin = imax = arr[1]  # 極小值、極大值
    start, end = 0, 0  # 峰值開始日期,結束日期後一天
    has_peak = False  # 是否有峰值

    for i in range(2, n-1):
        if arr[i] > arr[i-1]:  # 遞增,可能是新的峰值開始日期
            imax = arr[i]
            start = i
        elif arr[i] < arr[i-1]:    # 遞減,可能是峰值的結束日期後一天
            imin = arr[i]
            end = i

        if start != 0 and end != 0 and end > start and imax > imin:  # 找到峰值
            has_peak = True
            if end - start == 1:  # 只有一天
                print(f"{start:d} {imax:d}")
            else:  # 不只一天
                print(f"{start:d} {end - 1:d} {imax:d}")
            # 重置 start, imin, imax
            start = i
            imin = arr[i]
            imax = 0

    # 如果沒有峰值,輸出 0 0
    if not has_peak: print("0 0")



C++ 程式碼


使用時間約為 1 ms,記憶體約為 3.6 MB,通過測試。
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    vector<int> arr;
    while(getline(cin, s)) {
        arr.assign(1, 0);  // 開頭加一個 0
        stringstream ss (s);
        while(ss >> s) {
            arr.push_back(stoi(s));
        }
        
        int n = (int)arr.size();  // 天數加 1
        int start = 0, end = 0;  // 峰值開始日期、結束日期後一天
        int imin = arr[1], imax = arr[1];  // 極小值、極大值
        bool has_peak = false;  // 是否找到峰值
        for(int i = 2; i < n-1; i++) {  // 測試第 2 天到第 n-2 天
            if (arr[i] > arr[i-1]) {  // 1. 遞增,可能是新的峰值開始日期
                imax = arr[i];
                start = i;
            } else if (arr[i] < arr[i-1]) {  // 2. 遞減,可能是這個峰值結束日期後一天
                imin = arr[i];
                end = i;
            }
            
            // 如果 imax > imin 而且 end > start,結算這個峰值
            if (start != 0 && end != 0 && imax > imin && end > start) {
                has_peak = true;
                if (end - start == 1) {  // 只有一天
                    cout << start << " " << imax << "\n";
                } else {  // 不只一天,印出開始、結束日期
                    cout << start << " " << end - 1 << " " << imax << "\n";
                }
                start = i;  // 重置 start, imin, imax
                imin = arr[i];
                imax = 0;
            }
        }
        if (!has_peak) cout << "0 0\n";
    }
    return 0;
}


C 語言程式碼


使用時間約為 0 ms,記憶體約為 1.6 MB,通過測試。
#include <stdio.h>

int main() {
    // 讀取數量不確定的測資
    int arr[32], a, n = 1;  // 陣列,數值,天數
    while(scanf("%d", &a) != EOF) {
        arr[n] = a;
        n++;
    }
    
    // 找峰值
    int start = 0, end = 0;  // 峰值開始日期、結束日期後一天
    int imin = arr[1], imax = arr[1];  // 極小值、極大值
    int has_peak = 0;  // 是否找到峰值
    for(int i = 2; i < n-1; i++) {  // 測試第 2 天到第 n-2 天
        if (arr[i] > arr[i-1]) {  // 1. 遞增,可能是新的峰值開始日期
            imax = arr[i];
            start = i;
        } else if (arr[i] < arr[i-1]) {  // 2. 遞減,可能是這個峰值結束日期後一天
            imin = arr[i];
            end = i;
        }
            
        // 如果 imax > imin 而且 end > start,結算這個峰值
        if (start != 0 && end != 0 && imax > imin && end > start) {
            has_peak = 1;
            if (end - start == 1) {  // 只有一天
                printf("%d %d\n", start, imax);
            } else {  // 不只一天,印出開始、結束日期
                printf("%d %d %d\n", start, end - 1, imax);
            }
            start = i;  // 重置 start, imin, imax
            imin = arr[i];
            imax = 0;
        }
    }
    
    if (has_peak == 0) puts("0 0");
    return 0;
}


沒有留言:

張貼留言