標題:
202412新手1-旅遊計畫
[打印本頁]
作者:
may
時間:
2025-1-27 17:53
標題:
202412新手1-旅遊計畫
小鷗現在在歐洲留學，他最近剛好有 10 天的假期可以出去玩，他決定到 A 國旅遊。他發現飛機航班每天的價錢不太一樣，但住宿費用固定每天都是 1000 元。
請你幫小鷗決定他要在第幾天出發，第幾天回來，才可以將住宿加機票的總價壓到最低。當天來回則不會有任何的住宿費。
[attach]20601[/attach]
作者:
may
時間:
2025-1-27 18:25
#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 天）。
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)
Powered by Discuz! 7.2
