APCS實作題：程式交易

# APCS實作題2022年1月第1題：程式交易 > 日期：2023年9月22日 > 作者：王一哲 > 題目來源：111年1月實作題第1題 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=h081) ## 題目 ### 問題描述小明最近想要用程式做股票交易，給一個股票的歷史價格 $a[1], a[2], \dots, a[n]$，他的投資策略如下： 1. 同一個時間最多只會持有一張股票，並會在時間點 $1$ 花 $a[1]$ 買進。 2. 若當下持有股票且該股票買進價格為 $x$，當遇到價格 $y$ 大於等於 $D$ 時即賣出，並轉得利潤 $y-x$。 3. 若當下沒有持有股票且上一次的賣出價格為 $x$，當遇到價格 $y$ 小於等於 $x-D$ 時則會買進股票。輸出依照上述規則買賣後所得到的利潤和，若交易結束仍持有股票，則不考慮該股票買進的成本，直接無視該股票即可。 ### 輸入說明第一行輸入兩個正整數 $n, D$，接下來有 $n$ 個正整數，代表每個時間點股票的價格。數字範圍 - $1 \leq n, D \leq 100$ - $1 \leq a[i] \leq 100$ 子題配分 - 50%：$n = 3$ - 50%：無額外限制 ### 輸出說明輸出一個正整數，代表總利潤。 ### 範例一：輸入 ``` 3 10 50 20 45 ``` ### 範例一：正確輸出 ``` 0 ``` ### 範例二：輸入 ``` 6 10 30 20 45 38 10 20 ``` ### 範例二：正確輸出 ``` 25 ``` ## Python 程式碼於 ZeroJudge 測試結果，最長運算時間約為 21 ms，使用記憶體最多約為 3.3 MB，通過測試。 ```python= n, D = map(int, input().split()) # 讀取n, D a = list(map(int, input().split())) # 讀取股價資料a，索引值由0開始 cost, sell, profit, flag = a[0], 0, 0, True # 依序為買價、賣價、利潤、是否持有股票 for i in range(1, n): # 依序讀取 a[1] ~ a[n-1] if flag and a[i] - cost >= D: # 如果持有股票且價差大於等於D sell = a[i] # 更新賣價 profit += sell - cost # 更新利潤 flag = False # 未持有股票 elif not flag and a[i] <= sell - D: # 如果未持有股票且現價小於等於前一筆賣價減D cost = a[i] # 更新買價 flag = True # 持有股票 print(profit) # 印出利潤 ``` ## C++ 程式碼於 ZeroJudge 測試結果，最長運算時間約為 2 ms，使用記憶體最多約為 328 kB，通過測試。 ```cpp= #include <iostream> using namespace std; int main() { int n, D; cin >> n >> D; // 讀取n, D int a[n]; for(int i=0; i<n; i++) cin >> a[i]; // 讀取股價資料a，索引值由0開始 int cost = a[0], sell = 0, profit = 0; // 依序為買價、賣價、利潤 bool flag = true; // 是否持有股票 for(int i=1; i<n; i++) { // 依序讀取 a[1] ~ a[n-1] if (flag && a[i] - cost >= D) { // 如果持有股票且價差大於等於D sell = a[i]; // 更新賣價 profit += sell - cost; // 更新利潤 flag = false; // 未持有股票 } else if (!flag && a[i] <= sell - D) { // 如果未持有股票且現價小於等於前一筆賣價減D cost = a[i]; // 更新買價 flag = true; // 持有股票 } } cout << profit << endl; // 印出利潤 return 0; } ``` --- ###### tags:`APCS`、`Python`、`C++`