日期: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;
}
沒有留言:
張貼留言