【题目来源】洛谷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【输出样例】693【核心思想】问题分析给定三种出行方案的价格构成需要求最小花费。方案1为直飞价格a aa方案2为两段价格之和b c b cbc高铁到C CC市再飞机到B BB市方案3为两段价格之和b d b dbd高铁到C CC市再高铁到B BB市。问题本质是三个数值的最小值比较。算法选择直接比较计算三种方案的总价取最小值关键步骤读取输入a aaA → B A \to BA→B直飞、b bbA → C A \to CA→C高铁、c ccC → B C \to BC→B飞机、d ddC → B C \to BC→B高铁计算方案价格方案1P 1 a P_1 aP1​a方案2P 2 b c P_2 b cP2​bc方案3P 3 b d P_3 b dP3​bd输出最小值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分支无后效性三种方案相互独立不存在选择某方案后影响其他方案的情况因此无需动态规划或贪心策略适用于方案数极少、各方案价格可直接计算的简单决策问题【算法标签】#入门 #模拟【代码详解】#includebits/stdc.husingnamespacestd;inta,b,c,d;// a: A直飞B的价格; b: A高铁到C的价格; c: C飞机到B的价格; d: C高铁到B的价格intmain(){cinabcd;// 读入四种交通方式的价格coutmin({a,bc,bd});// 输出三种方案的最小值直飞 / 高铁飞机 / 高铁高铁return0;}【运行结果】999 105 699 588 693