本文分享的必刷题目是从蓝桥云课、洛谷、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 < ba<b和x < y x < yx<y，简化后续计算
关键步骤：
- 读取输入：a , b , x , y a, b, x, ya,b,x,y
- 排序规范化：
- 若x > y x > yx>y：交换x , y x, yx,y
- 若a > b a > ba>b：交换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 < ba<b和x < y x < yx<y，消除绝对值带来的分类讨论复杂度
- 传送门单向最优性：由于传送是双向且瞬时的，从a aa到较近端x xx、从较远端y yy到b bb总是最优（已排序前提下）
- 适用于"两种策略选优"类基础问题，核心是直接比较所有可行方案
【解题思路】
【算法标签】
#入门 #贪心
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;inta,b,x,y,ans=0;// ifstream filein("teleport.in");// ofstream fileout("teleport.out");intmain(){cin>>a>>b>>x>>y;// 输入a、b、x和yif(x>y)swap(x,y);// 保证x小于yif(a>b)swap(a,b);// 保证a小于bans=min(abs(b-a),abs(x-a)+abs(y-b));// 计算b与a的距离，以及通过传送门的距离（即a->x->y->b）的最小值cout<<ans<<endl;// 打印结果return0;}【运行结果】
3 10 8 2 3
