- #include <bits/stdc++.h>
- //#include <iostream>
- //#include <vector>
- //#include <climits>
- using namespace std;
- int main() {
- // 定義變數
- const int n = 10; // 假期天數固定為 10 天
- vector<int> departureCost(n); // 去程票價
- vector<int> returnCost(n); // 回程票價
- // 輸入去程票價
- for (int i = 0; i < n; i++) {
- cin >> departureCost[i];
- }
- // 輸入回程票價
- for (int i = 0; i < n; i++) {
- cin >> returnCost[i];
- }
- const int dailyHotelCost = 1000; // 每天住宿費用
- int minCost = INT_MAX; // 最小總成本
- int bestStartDay = 0; // 最佳出發日
- int bestEndDay = 0; // 最佳回程日
- // 枚舉所有可能的出發日和回程日
- for (int start = 0; start < n; start++) {
- for (int end = start; end < n; end++) {
- // 計算總成本
- int totalCost = departureCost[start] + returnCost[end] + (end - start) * dailyHotelCost;
- // 更新最小總成本及最佳出發日、回程日
- if (totalCost < minCost) {
- minCost = totalCost;
- bestStartDay = start + 1; // 轉換為 1 基底
- bestEndDay = end + 1; // 轉換為 1 基底
- }
- }
- }
- // 輸出結果
- cout << bestStartDay << " " << bestEndDay << " " << minCost << endl;
- return 0;
- }
- /*
- 1 10000 10000 10000 1 10000 10000 10000 10000 10000
- 10000 10000 10000 10000 10000 10000 10000 10000 10000 1
- */
解題邏輯
輸入資料解析：
第一行輸入 10 個整數，表示每天的去程票價。
第二行輸入 10 個整數，表示每天的回程票價。
設定住宿費用固定為 1000 元。
問題建模：
找到一個區間 [A, B]（第 A 天出發，第 B 天回來），使總成本最低。
總成本公式為：
總成本 = 去程票價[A-1] + 回程票價[B-1] + (B - A) * 1000
若 A == B，則無住宿費用。
解法步驟：
使用雙重迴圈枚舉所有可能的出發日與回程日 [A, B]。
計算總成本，更新最小成本及對應的 A 和 B。
輸出結果：
輸出最低總成本的出發日 A、回程日 B，以及對應的總成本 S。
-----------------------------------------------------
程式說明
輸入部分：
利用 vector<int> 儲存去程與回程票價。
假期天數固定為 10 天。
核心邏輯：
外層迴圈枚舉出發日 start。
內層迴圈枚舉回程日 end。
使用公式計算總成本：
總成本 = 去程票價[start] + 回程票價[end] + (end - start) * 1000
更新最低總成本與對應的出發日與回程日。
輸出部分：
輸出最低總成本的出發日、回程日及總成本。
時間複雜度
O(n²)：雙重迴圈枚舉所有可能的出發日與回程日。
此程式適用於天數固定較小的情況（如 10 天）。 |
