当前位置：首页 > news >正文

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

news 2026/7/4 16:58:47

【题目来源】

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

【题目描述】

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

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

从A AA市直飞B BB市；
从A AA市坐高铁到C CC市，然后坐飞机到B BB市；
从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

【输出样例】

【核心思想】

问题分析：给定三种出行方案的价格构成，需要求最小花费。方案1为直飞价格a aa；方案2为两段价格之和b + c b + cb+c（高铁到C CC市再飞机到B BB市）；方案3为两段价格之和b + d b + db+d（高铁到C CC市再高铁到B BB市）。问题本质是三个数值的最小值比较。
算法选择：
- 直接比较：计算三种方案的总价，取最小值
关键步骤：
- 读取输入：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)
时间/空间复杂度：
- 时间复杂度：O ( 1 ) O(1)O(1)，固定次数的输入和比较操作
- 空间复杂度：O ( 1 ) O(1)O(1)，仅使用四个变量
入门模拟的核心思想：
- 问题转化：将复杂的出行方案描述抽象为简单的算术表达式，方案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;}