欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客
【题目来源】
洛谷：[P1677 USACO18FEB] Hoofball B - 洛谷 (luogu.com.cn)
【题目描述】
为了准备即将到来的蹄球锦标赛，Farmer John正在训练他的N头奶牛（方便起见，编号为**1 … N 1\dots N1…N，其中1 ≤ N ≤ 100 1\le N\le 1001≤N≤100）进行传球。这些奶牛在牛棚一侧沿直线排列，第i ii号奶牛位于距离牛棚x i x_ixi的地方( 1 ≤ x i ≤ 1000 ) (1\le x_i\le 1000)(1≤xi≤1000)**。每头奶牛都在不同的位置上。
在训练开始的时候，Farmer John会将若干个球传给不同的奶牛。当第**i ii**号奶牛接到球时，无论是从Farmer John或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会传给其中距左边最远的那头奶牛）。为了使所有奶牛都有机会练习到传球，Farmer John想要确保每头奶牛都持球至少一次。帮助他求出为了达到这一目的他开始时至少要传出的球的数量。假设他在开始的时候能将球传给最适当的一组奶牛。
【输入】
输入的第一行包含N NN。第二行包含N NN个用空格分隔的整数，其中第i ii个整数为**x i x_ixi**。
【输出】
输出Farmer John开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。
【输入样例】
5 7 1 3 11 4【输出样例】
2【算法标签】
《洛谷 P1677 HoofBall》 #模拟# #排序# #深度优先搜索,DFS# #USACO# #O2优化# #2018#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intn;// 奶牛的数量inta[105];// 存储奶牛的位置坐标intcnt[105];// 计数器，记录每个位置被指向的次数intnxt[105];// 记录每个奶牛传球的方向（下一个奶牛的位置）intans=0;// 需要的最少球数// 文件输入输出流（注释掉的代码）// ifstream filein("hoofball.in");// ofstream fileout("hoofball.out");intmain(){// 输入奶牛数量cin>>n;// 输入奶牛的位置坐标for(inti=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(inti=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(inti=1;i<=n;i++){// 如果某个奶牛没有被任何其他奶牛指向（cnt[i]==0）// 说明需要在这个位置放一个球if(cnt[i]==0){ans++;}}// 第二轮统计：处理互相传球的情况（循环传球）for(inti=1;i<n;i++){// 检查相邻两个奶牛是否形成互相传球的关系if(cnt[i]==1&&cnt[i+1]==1&&// 两个奶牛都只被指向一次nxt[i]==i+1&&nxt[i+1]==i)// 互相指向对方{// 这种循环传球的情况需要额外放一个球ans++;}}// 输出最少需要的球数cout<<ans<<endl;return0;}【运行结果】
5 7 1 3 11 4 2
