202412新手1-旅遊計畫

may

小鷗現在在歐洲留學，他最近剛好有 10 天的假期可以出去玩，他決定到 A 國旅遊。他發現飛機航班每天的價錢不太一樣，但住宿費用固定每天都是 1000 元。
請你幫小鷗決定他要在第幾天出發，第幾天回來，才可以將住宿加機票的總價壓到最低。當天來回則不會有任何的住宿費。

may

1. #include <bits/stdc++.h>
   
2. //#include <iostream>
   
3. //#include <vector>
   
4. //#include <climits>
   
5. using namespace std;
   
6. 
   
7. int main() {
   
8.     // 定義變數
   
9.     const int n = 10; // 假期天數固定為 10 天
   
10.     vector<int> departureCost(n); // 去程票價
    
11.     vector<int> returnCost(n);    // 回程票價
    
12. 
    
13.     // 輸入去程票價
    
14.     for (int i = 0; i < n; i++) {
    
15.         cin >> departureCost[i];
    
16.     }
    
17. 
    
18.     // 輸入回程票價
    
19.     for (int i = 0; i < n; i++) {
    
20.         cin >> returnCost[i];
    
21.     }
    
22. 
    
23.     const int dailyHotelCost = 1000; // 每天住宿費用
    
24.     int minCost = INT_MAX;           // 最小總成本
    
25.     int bestStartDay = 0;            // 最佳出發日
    
26.     int bestEndDay = 0;              // 最佳回程日
    
27. 
    
28.     // 枚舉所有可能的出發日和回程日
    
29.     for (int start = 0; start < n; start++) {
    
30.         for (int end = start; end < n; end++) {
    
31.             // 計算總成本
    
32.             int totalCost = departureCost[start] + returnCost[end] + (end - start) * dailyHotelCost;
    
33. 
    
34.             // 更新最小總成本及最佳出發日、回程日
    
35.             if (totalCost < minCost) {
    
36.                 minCost = totalCost;
    
37.                 bestStartDay = start + 1; // 轉換為 1 基底
    
38.                 bestEndDay = end + 1;     // 轉換為 1 基底
    
39.             }
    
40.         }
    
41.     }
    
42. 
    
43.     // 輸出結果
    
44.     cout << bestStartDay << " " << bestEndDay << " " << minCost << endl;
    
45. 
    
46.     return 0;
    
47. }
    
48. /*
    
49. 1 10000 10000 10000 1 10000 10000 10000 10000 10000
    
50. 10000 10000 10000 10000 10000 10000 10000 10000 10000 1
    
51. */

複製代碼

------------------------------------------------------------------
解題邏輯
輸入資料解析：

第一行輸入 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 天）。