【题目来源】

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

【题目描述】

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

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

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

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

【输入】

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

• 第 $1$ 行的正整数表示「从 $A$ 市直飞 $B$ 市」的价格；
• 第 $2$ 行的正整数表示「从 $A$ 市坐高铁到 $C$ 市」的价格；
• 第 $3$ 行的正整数表示「从 $C$ 市坐飞机到 $B$ 市」的价格；
• 第 $4$ 行的正整数表示「从 $C$ 市坐高铁到 $B$ 市」的价格。

【输出】

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

【输入样例】

999
105
699
588

【输出样例】

693

【核心思想】

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

2. 算法选择：

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

3. 关键步骤：

   • 读取输入：$a$（$A\to B$ 直飞）、$b$（$A\to C$ 高铁）、$c$（$C\to B$ 飞机）、$d$（$C\to B$ 高铁）
   • 计算方案价格：
     • 方案1：$P_1=a$
     • 方案2：$P_2=b+c$
     • 方案3：$P_3=b+d$
   • 输出最小值：$\min (P_1,P_2,P_3)$

4. 时间/空间复杂度：

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

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

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

【算法标签】

#入门 #模拟

【代码详解】

#include <bits/stdc++.h>
using namespace std;

int a, b, c, d;                    // a: A直飞B的价格; b: A高铁到C的价格; c: C飞机到B的价格; d: C高铁到B的价格

int main()
{
    cin >> a >> b >> c >> d;       // 读入四种交通方式的价格

    cout << min({a, b + c, b + d});  // 输出三种方案的最小值：直飞 / 高铁+飞机 / 高铁+高铁

    return 0;
}

【运行结果】

999
105
699
588
693