本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1693 [USACO19FEB] Sleepy Cow Herding B - 洛谷luogu.com.cn)【题目描述】Farmer John的三头获奖奶牛Bessie、Elsie和Mildred总是会迷路走到农场上遥远的地方去他需要你帮助将她们一起赶回来。农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴奶牛可以占据数轴上的任意整数位置。这3头奶牛现在正位于不同的整数位置Farmer John想要移动她们使得她们占据三个相邻的位置例如位置6 66、7 77、8 88。不幸的是奶牛们现在很困Farmer John要让她们集中精力听从命令移动并不容易。任意时刻他只能使得一头处在“端点”在所有奶牛中位置最小或最大位置的奶牛移动。当他移动奶牛时他可以命令她走到任意一个未被占用的整数位置只要在新的位置上她不再是一个端点。可以看到随着时间的推移这样的移动可以使奶牛们趋向越来越近。请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。【输入】输入包含一行包括三个空格分隔的整数为Bessie、Elsie和Mildred的位置。每个位置均为一个范围1 … 10 9 1\dots 10^91…109内的整数。【输出】输出的第一行包含Farmer John需要将奶牛们聚集起来所需进行的最小移动次数。第二行包含他将奶牛聚集起来能够进行的最大移动次数。【输入样例】4 7 9【输出样例】1 2【核心思想】问题分析给定三头奶牛在数轴上的位置每次只能移动端点位置的奶牛到任意未被占用的整数位置且移动后该奶牛不能仍是端点。求使三头奶牛占据三个相邻位置的最小和最大移动次数。这是一个分类讨论/直接模拟问题关键在于分析三头奶牛的相对位置间隔根据间隔大小直接判定最小和最大步数。算法选择排序 间隔分析先排序得到a 1 a 2 a 3 a_1 a_2 a_3a1​a2​a3​计算两个间隔d 1 a 2 − a 1 d_1 a_2 - a_1d1​a2​−a1​、d 2 a 3 − a 2 d_2 a_3 - a_2d2​a3​−a2​分类讨论根据( d 1 , d 2 ) (d_1, d_2)(d1​,d2​)的不同组合直接输出对应的最小和最大移动次数关键步骤读取输入三个整数位置排序sort(a1, a4)得到有序位置a 1 , a 2 , a 3 a_1, a_2, a_3a1​,a2​,a3​计算间隔d 1 a 2 − a 1 d_1 a_2 - a_1d1​a2​−a1​d 2 a 3 − a 2 d_2 a_3 - a_2d2​a3​−a2​分类判断已相邻d 1 1 d_1 1d1​1且d 2 1 d_2 1d2​1最小 最大 0 00一步可达( d 1 2 (d_1 2(d1​2且d 2 1 ) d_2 1)d2​1)或( d 1 1 (d_1 1(d1​1且d 2 2 ) d_2 2)d2​2)或( d 1 2 (d_1 2(d1​2且d 2 2 ) d_2 2)d2​2)最小 最大 1 11间隔一大一小若d 1 2 d_1 2d1​2且d 2 1 d_2 1d2​1或d 1 1 d_1 1d1​1且d 2 2 d_2 2d2​2最小 2 22若d 1 2 d_1 2d1​2且d 2 2 d_2 2d2​2或d 1 2 d_1 2d1​2且d 2 2 d_2 2d2​2最小 1 11最大 max ⁡ ( d 1 − 1 , d 2 − 1 ) \max(d_1 - 1, d_2 - 1)max(d1​−1,d2​−1)间隔均大于2 22最小 2 22最大 max ⁡ ( d 1 − 1 , d 2 − 1 ) \max(d_1 - 1, d_2 - 1)max(d1​−1,d2​−1)时间/空间复杂度时间复杂度O ( 1 ) O(1)O(1)仅排序和若干次比较空间复杂度O ( 1 ) O(1)O(1)仅需存储三个位置分类讨论的核心思想端点移动约束只能移动最小或最大位置的奶牛且移动后不能仍是端点这意味着端点奶牛必须移动到中间区域最小步数分析若存在间隔为2 22可将中间奶牛或端点奶牛一步移动到间隔处使三者连续若两个间隔均≥ 3 \ge 3≥3至少需要2 22步先移动一个端点缩小间隔再调整最大步数分析每次只移动一步到相邻空位最大步数 较大间隔− 1 - 1−1逐格移动端点向中间靠拢适用于小规模约束移动 极值分析类问题核心是通过间隔分类直接得出答案【解题思路】【算法标签】#普及- #模拟【代码详解】#includebits/stdc.husingnamespacestd;inta[5];// 存储三个奶牛的位置intminn0;// 最小移动次数intmaxn0;// 最大移动次数// 文件输入输出流注释掉的代码// ifstream filein(herding.in);// ofstream fileout(herding.out);intmain(){// 输入三个奶牛的位置for(inti1;i3;i){// cin a[i];// filein a[i];cina[i];}// 对三个位置进行排序从小到大sort(a1,a31);// 情况1三个奶牛已经连续相邻间隔都为1if(a[2]-a[1]1a[3]-a[2]1){// 无需移动cout0endl0endl;}// 情况2两个间隔分别为2和1如1,3,4 或 1,2,4elseif((a[2]-a[1]2a[3]-a[2]1)||(a[2]-a[1]1a[3]-a[2]2)){// 只需要移动一次即可使三个奶牛连续cout1endl1endl;}// 情况3两个间隔都为2如1,3,5elseif(a[2]-a[1]2a[3]-a[2]2){// 只需要移动一次即可使三个奶牛连续cout1endl1endl;}// 情况4一个间隔大于2另一个间隔为1如1,4,5 或 1,2,5elseif((a[2]-a[1]2a[3]-a[2]1)||(a[2]-a[1]1a[3]-a[2]2)){minn2;// 最小需要移动2次maxnmax(a[2]-a[1]-1,a[3]-a[2]-1);// 最大移动次数为较大间隔减1coutminnendlmaxnendl;}// 情况5一个间隔大于2另一个间隔为2如1,4,6 或 1,3,6elseif((a[2]-a[1]2a[3]-a[2]2)||(a[2]-a[1]2a[3]-a[2]2)){minn1;// 最小需要移动1次maxnmax(a[2]-a[1]-1,a[3]-a[2]-1);// 最大移动次数为较大间隔减1coutminnendlmaxnendl;}// 情况6两个间隔都大于2如1,5,10elseif(a[2]-a[1]2a[3]-a[2]2){minn2;// 最小需要移动2次maxnmax(a[2]-a[1]-1,a[3]-a[2]-1);// 最大移动次数为较大间隔减1coutminnendlmaxnendl;}return0;}【运行结果】4 7 9 1 2