【题目来源】

洛谷：B4551 [GESP202606 一级] 去旅行 - 洛谷

【题目描述】

快暑假了，小杨同学正在计划出去旅行，前往目的地的方案多种多样，小杨同学想知道如何前往目的地最便宜。

小杨同学住在A AA市，旅行目的地是B BB市，小杨同学前往目的地有三种方案：

1. 从A AA市直飞B BB市；
2. 从A AA市坐高铁到C CC市，然后坐飞机到B BB市；
3. 从A AA市坐高铁到C CC市，然后坐高铁到B BB市。

请帮小杨同学求出最便宜的出行方案的价格。

【输入】

输入包含4 44行，每行一个正整数：

• 第1 11行的正整数表示「从A AA市直飞B BB市」的价格；
• 第2 22行的正整数表示「从A AA市坐高铁到C CC市」的价格；
• 第3 33行的正整数表示「从C CC市坐飞机到B BB市」的价格；
• 第4 44行的正整数表示「从C CC市坐高铁到B BB市」的价格。

【输出】

输出一个正整数，表示3 33种方式中，最便宜的出行方案的价格。

【输入样例】

999 105 699 588

【输出样例】

693

【核心思想】

1. 问题分析：给定三种出行方案的价格构成，需要求最小花费。方案1为直飞价格a aa；方案2为两段价格之和b + c b + cb+c（高铁到C CC市再飞机到B BB市）；方案3为两段价格之和b + d b + db+d（高铁到C CC市再高铁到B BB市）。问题本质是三个数值的最小值比较。

2. 算法选择：

   • 直接比较：计算三种方案的总价，取最小值

3. 关键步骤：

   • 读取输入：a aa（A → B A \to BA→B直飞）、b bb（A → C A \to CA→C高铁）、c cc（C → B C \to BC→B飞机）、d dd（C → B C \to BC→B高铁）
   • 计算方案价格：
     • 方案1：P 1 = a P_1 = aP1​=a
     • 方案2：P 2 = b + c P_2 = b + cP2​=b+c
     • 方案3：P 3 = b + d P_3 = b + dP3​=b+d
   • 输出最小值：min ⁡ ( P 1 , P 2 , P 3 ) \min(P_1, P_2, P_3)min(P1​,P2​,P3​)

4. 时间/空间复杂度：

   • 时间复杂度：O ( 1 ) O(1)O(1)，固定次数的输入和比较操作
   • 空间复杂度：O ( 1 ) O(1)O(1)，仅使用四个变量

5. 入门模拟的核心思想：

   • 问题转化：将复杂的出行方案描述抽象为简单的算术表达式，方案2和方案3共享第一段b bb，但比较时无需利用此特性，直接计算总和即可
   • 多值取最小：利用min函数（或手写比较）直接对三个表达式求最小，避免冗余的if-else分支
   • 无后效性：三种方案相互独立，不存在选择某方案后影响其他方案的情况，因此无需动态规划或贪心策略
   • 适用于方案数极少、各方案价格可直接计算的简单决策问题

【算法标签】

#入门 #模拟

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;inta,b,c,d;// a: A直飞B的价格; b: A高铁到C的价格; c: C飞机到B的价格; d: C高铁到B的价格intmain(){cin>>a>>b>>c>>d;// 读入四种交通方式的价格cout<<min({a,b+c,b+d});// 输出三种方案的最小值：直飞 / 高铁+飞机 / 高铁+高铁return0;}

【运行结果】

999 105 699 588 693