欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客
P1639 Teleportation
【题目来源】
洛谷：[P1639 USACO18FEB] Teleportation B - 洛谷
【题目描述】
Farmer John 最讨厌的农活是运输牛粪。为了精简这个过程，他制造了一个伟大的发明：便便传送门！与使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点相比，他可以使用便便传送门将牛粪从一个地点瞬间传送到另一个地点。
Farmer John 的农场沿着一条长直道路而建，所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示（相当于数轴上的一个点）。一个传送门可以用两个数 \(x\) 和 \(y\) 表示，被拖到地点 \(x\) 的牛粪可以瞬间传送到地点 \(y\)，反之亦然。
Farmer John 想要将牛粪从地点 \(a\) 运输到地点 \(b\)，他建造了一个可能对这一过程有所帮助的传送门（当然，如果没有帮助，他也可以不用）。请帮助他求出他需要使用拖拉机运输牛粪的总距离的最小值。
【输入】
输入仅包含一行，为四个用空格分隔的整数：\(a\) 和 \(b\)，表示起始地点和结束地点，后面是 \(x\) 和 \(y\)，表示传送门。所有的位置都是范围为 \(0\ldots 100\) 的整数，不一定各不相同。
【输出】
输出一个整数，为 Farmer John 需要用拖拉机运输牛粪的最小距离。
【输入样例】
3 10 8 2
【输出样例】
3
【解题思路】
【算法标签】
《洛谷 P1639 Teleportation》 #贪心# #USACO# #O2优化# #2018#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int a, b, x, y, ans=0;
// ifstream filein("teleport.in");
// ofstream fileout("teleport.out");
int main()
{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; // 打印结果return 0;
}
【运行结果】
3 10 8 2
3
P1677 HoofBall
【题目来源】
洛谷：[P1677 USACO18FEB] Hoofball B - 洛谷 (luogu.com.cn)
【题目描述】
为了准备即将到来的蹄球锦标赛，Farmer John正在训练他的N头奶牛（方便起见，编号为\(1\dots N\)，其中\(1\le N\le 100\)）进行传球。这些奶牛在牛棚一侧沿直线排列，第\(i\)号奶牛位于距离牛棚\(x_i\)的地方\((1\le x_i\le 1000)\)。每头奶牛都在不同的位置上。
在训练开始的时候，Farmer John会将若干个球传给不同的奶牛。当第\(i\)号奶牛接到球时，无论是从Farmer John或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会传给其中距左边最远的那头奶牛）。为了使所有奶牛都有机会练习到传球，Farmer John想要确保每头奶牛都持球至少一次。帮助他求出为了达到这一目的他开始时至少要传出的球的数量。假设他在开始的时候能将球传给最适当的一组奶牛。
【输入】
输入的第一行包含\(N\)。第二行包含\(N\)个用空格分隔的整数，其中第\(i\)个整数为\(x_i\)。
【输出】
输出Farmer John开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。
【输入样例】
5
7 1 3 11 4
【输出样例】
2
【解题思路】
【算法标签】
《洛谷 P1677 HoofBall》 #模拟# #排序# #深度优先搜索,DFS# #USACO# #O2优化# #2018#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 奶牛的数量
int a[105]; // 存储奶牛的位置坐标
int cnt[105]; // 计数器，记录每个位置被指向的次数
int nxt[105]; // 记录每个奶牛传球的方向（下一个奶牛的位置）
int ans = 0; // 需要的最少球数// 文件输入输出流（注释掉的代码）
// ifstream filein("hoofball.in");
// ofstream fileout("hoofball.out");int main()
{// 输入奶牛数量cin >> n;// 输入奶牛的位置坐标for (int i = 1; i <= n; i++){cin >> a[i];}// 对奶牛位置进行升序排序sort(a + 1, a + n + 1);// 处理左端点（第一个奶牛）nxt[1] = 2; // 最左边的奶牛只能向右传球cnt[2] = 1; // 第二个奶牛被指向一次// 处理右端点（最后一个奶牛）nxt[n] = n - 1; // 最右边的奶牛只能向左传球cnt[n - 1] = 1; // 倒数第二个奶牛被指向一次// 处理中间位置的奶牛（从第2个到倒数第2个）for (int i = 2; i < n; i++){// 比较向左和向右的距离，选择较近的方向if (a[i] - a[i - 1] > a[i + 1] - a[i]){// 向右传球（右边更近）nxt[i] = i + 1; // 记录传球方向为右边cnt[i + 1]++; // 右边奶牛被指向次数加1}else{// 向左传球（左边更近）nxt[i] = i - 1; // 记录传球方向为左边cnt[i - 1]++; // 左边奶牛被指向次数加1}}// 第一轮统计：找出没有被指向的奶牛（需要放球的位置）for (int i = 1; i <= n; i++){// 如果某个奶牛没有被任何其他奶牛指向（cnt[i]==0）// 说明需要在这个位置放一个球if (cnt[i] == 0){ans++;}}// 第二轮统计：处理互相传球的情况（循环传球）for (int i = 1; i < n; i++){// 检查相邻两个奶牛是否形成互相传球的关系if (cnt[i] == 1 && cnt[i + 1] == 1 && // 两个奶牛都只被指向一次nxt[i] == i + 1 && nxt[i + 1] == i) // 互相指向对方{// 这种循环传球的情况需要额外放一个球ans++;}}// 输出最少需要的球数cout << ans << endl;return 0;
}
【运行结果】
5
7 1 3 11 4
2