题解：洛谷 P1639 [USACO18FEB] Teleportation B

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1639 [USACO18FEB] Teleportation B - 洛谷【题目描述】Farmer John 最讨厌的农活是运输牛粪。为了精简这个过程他制造了一个伟大的发明便便传送门与使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点相比他可以使用便便传送门将牛粪从一个地点瞬间传送到另一个地点。Farmer John 的农场沿着一条长直道路而建所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示相当于数轴上的一个点。一个传送门可以用两个数x xx和y yy表示被拖到地点x xx的牛粪可以瞬间传送到地点y yy反之亦然。Farmer John 想要将牛粪从地点a aa运输到地点b bb他建造了一个可能对这一过程有所帮助的传送门当然如果没有帮助他也可以不用。请帮助他求出他需要使用拖拉机运输牛粪的总距离的最小值。【输入】输入仅包含一行为四个用空格分隔的整数a aa和b bb表示起始地点和结束地点后面是x xx和y yy表示传送门。所有的位置都是范围为0 … 100 0\ldots 1000…100的整数不一定各不相同。【输出】输出一个整数为 Farmer John 需要用拖拉机运输牛粪的最小距离。【输入样例】3 10 8 2【输出样例】3【核心思想】问题分析给定起点a aa、终点b bb和传送门( x , y ) (x, y)(x,y)FJ 可以选择直接步行从a aa到b bb或步行到传送门一端x xx或y yy瞬间传送到另一端再步行到b bb。求最小总步行距离。这是一个贪心/分类讨论问题关键在于比较直接走与使用传送门两种方案的距离。算法选择直接比较答案 min ⁡ ( 直接距离 , 传送门方案距离 ) \min(\text{直接距离},\ \text{传送门方案距离})min(直接距离,传送门方案距离)排序规范化通过交换保证a b a bab和x y x yxy简化后续计算关键步骤读取输入a , b , x , y a, b, x, ya,b,x,y排序规范化若x y x yxy交换x , y x, yx,y若a b a bab交换a , b a, ba,b计算两种方案直接走∣ b − a ∣ |b - a|∣b−a∣使用传送门∣ x − a ∣ ∣ y − b ∣ |x - a| |y - b|∣x−a∣∣y−b∣从a aa走到x xx传送到y yy再走到b bb输出min ⁡ ( 直接走 , 传送门 ) \min(\text{直接走},\ \text{传送门})min(直接走,传送门)时间/空间复杂度时间复杂度O ( 1 ) O(1)O(1)仅若干次绝对值和取最小值空间复杂度O ( 1 ) O(1)O(1)仅需常数个变量贪心分类讨论的核心思想最优子结构全局最优 两种独立方案直接/传送的局部最优取较小对称性消除通过排序保证a b a bab和x y x yxy消除绝对值带来的分类讨论复杂度传送门单向最优性由于传送是双向且瞬时的从a aa到较近端x xx、从较远端y yy到b bb总是最优已排序前提下适用于两种策略选优类基础问题核心是直接比较所有可行方案【解题思路】【算法标签】#入门 #贪心【代码详解】#includebits/stdc.husingnamespacestd;inta,b,x,y,ans0;// ifstream filein(teleport.in);// ofstream fileout(teleport.out);intmain(){cinabxy;// 输入a、b、x和yif(xy)swap(x,y);// 保证x小于yif(ab)swap(a,b);// 保证a小于bansmin(abs(b-a),abs(x-a)abs(y-b));// 计算b与a的距离以及通过传送门的距离即a-x-y-b的最小值coutansendl;// 打印结果return0;}【运行结果】3 10 8 2 3