![题解：洛谷 P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G](http://pic.xiahunao.cn/yaotu/题解：洛谷 P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G)
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G - 洛谷【题目描述】农夫约翰建造了一座有n nn间牛舍的小屋牛舍排在一条直线上第i ii间牛舍在x i x_ixi的位置但是约翰的m mm头牛对小屋很不满意因此经常互相攻击。约翰为了防止牛之间互相伤害因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。牛们并不喜欢这种布局而且几头牛放在一个隔间里它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间使任意两头牛之间的最小距离尽可能的大那么这个最大的最小距离是多少呢【输入】第一行用空格分隔的两个整数n nn和m mm下面n nn行为n nn个用空格隔开的整数表示位置x i x_ixi。【输出】一行一个整数表示最大的最小距离值。【输入样例】5 3 1 2 8 4 9【输出样例】3【核心思想】问题分析给定n nn个牛舍的直线位置和m mm头牛需要将m mm头牛放入牛舍使得任意两头牛之间的最小距离最大化。这是一个整数二分 贪心验证问题关键在于将最大化最小距离转化为二分判定问题用贪心策略验证给定距离d dd是否可行。算法选择整数二分在距离范围[ 1 , max ( x i ) − min ( x i ) ] [1, \max(x_i) - \min(x_i)][1,max(xi)−min(xi)]内二分查找最大的可行最小距离贪心验证对于给定的候选距离m i d midmid从左到右贪心放置牛第一头放最左之后每头放在距离上一头至少m i d midmid的最左位置统计能放多少头关键步骤读取输入n , m n, mn,m和n nn个位置x i x_ixi排序sort(a1, an1)使位置有序二分初始化l 1 l 1l1r a [ n ] − a [ 1 ] r a[n] - a[1]ra[n]−a[1]最大可能距离二分过程l r l rlrm i d l ( r − l ) / 2 mid l (r - l) / 2midl(r−l)/2贪心验证last a[1]c n t 1 cnt 1cnt1第一头放最左遍历i ii从2 22到n nn若a [ i ] − l a s t ≥ m i d a[i] - last \ge mida[i]−last≥mid则c n t 1 cnt \mathrel{} 1cnt1last a[i]判定若c n t ≥ m cnt \ge mcnt≥m距离m i d midmid可行尝试更大l m i d 1 l mid 1lmid1若c n t m cnt mcntm距离m i d midmid不可行尝试更小r m i d r midrmid输出l − 1 l - 1l−1最终l ll指向第一个不可行的距离时间/空间复杂度时间复杂度O ( n log ( max x i ) ) O(n \log (\max x_i))O(nlog(maxxi))二分O ( log ( max x i ) ) O(\log (\max x_i))O(log(maxxi))轮每轮贪心验证O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)存储位置数组整数二分 贪心验证的核心思想单调性若距离d dd可行能放m mm头牛则所有≤ d \le d≤d的距离也可行若d dd不可行则所有 d dd的距离均不可行。满足二分条件贪心最优性对于固定的d dd从左到右尽可能早地放牛能为后续留下更多空间是验证d dd是否可行的最优策略最大化最小值的经典框架最大化最小距离/最小化最大距离类问题通常转化为二分 贪心验证适用于资源分配 间距约束类问题核心是利用单调性二分搜索并用贪心验证可行性【解题思路】【算法标签】#普及- #整数二分【代码详解】#includebits/stdc.husingnamespacestd;intn,m,l,r,mid;inta[100005];intmain(){cinnm;// 输入n和mfor(inti1;in;i){// 输入n个牛舍的位置cina[i];}sort(a1,an1);// 按照从小到大排列因为后面需要二分搜索la[1],ra[n];// 定义l和rwhile(lr){// 二分模板intcnt0;// 统计可选择的牛舍midl(r-l)/2;// 二分模板intlasta[1];// 定义待比较的牛舍初始从第1个牛舍开始比较for(inti2;in;i){// 往后遍历所有牛舍if(a[i]-lastmid){// 如果两个牛舍之间的距离大于等于mid即可以被选择cnt;// 统计数自增1lasta[i];}}// cout cnt cnt endl;if(cntm-1)rmid;elselmid1;}coutl-1endl;// 因为r先动所以最终输出应该是l-1l最后1试探失败所以需要l-1即为midreturn0;}【运行结果】5 3 1 2 8 4 9 3 
长河君 · 2026/10/24 5:26:33 · 阅读 1.2k 题解：洛谷 P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G - 洛谷【题目描述】农夫约翰建造了一座有n nn间牛舍的小屋牛舍排在一条直线上第i ii间牛舍在x i x_ixi的位置但是约翰的m mm头牛对小屋很不满意因此经常互相攻击。约翰为了防止牛之间互相伤害因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。牛们并不喜欢这种布局而且几头牛放在一个隔间里它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间使任意两头牛之间的最小距离尽可能的大那么这个最大的最小距离是多少呢【输入】第一行用空格分隔的两个整数n nn和m mm下面n nn行为n nn个用空格隔开的整数表示位置x i x_ixi。【输出】一行一个整数表示最大的最小距离值。【输入样例】5 3 1 2 8 4 9【输出样例】3【核心思想】问题分析给定n nn个牛舍的直线位置和m mm头牛需要将m mm头牛放入牛舍使得任意两头牛之间的最小距离最大化。这是一个整数二分 贪心验证问题关键在于将最大化最小距离转化为二分判定问题用贪心策略验证给定距离d dd是否可行。算法选择整数二分在距离范围[ 1 , max ( x i ) − min ( x i ) ] [1, \max(x_i) - \min(x_i)][1,max(xi)−min(xi)]内二分查找最大的可行最小距离贪心验证对于给定的候选距离m i d midmid从左到右贪心放置牛第一头放最左之后每头放在距离上一头至少m i d midmid的最左位置统计能放多少头关键步骤读取输入n , m n, mn,m和n nn个位置x i x_ixi排序sort(a1, an1)使位置有序二分初始化l 1 l 1l1r a [ n ] − a [ 1 ] r a[n] - a[1]ra[n]−a[1]最大可能距离二分过程l r l rlrm i d l ( r − l ) / 2 mid l (r - l) / 2midl(r−l)/2贪心验证last a[1]c n t 1 cnt 1cnt1第一头放最左遍历i ii从2 22到n nn若a [ i ] − l a s t ≥ m i d a[i] - last \ge mida[i]−last≥mid则c n t 1 cnt \mathrel{} 1cnt1last a[i]判定若c n t ≥ m cnt \ge mcnt≥m距离m i d midmid可行尝试更大l m i d 1 l mid 1lmid1若c n t m cnt mcntm距离m i d midmid不可行尝试更小r m i d r midrmid输出l − 1 l - 1l−1最终l ll指向第一个不可行的距离时间/空间复杂度时间复杂度O ( n log ( max x i ) ) O(n \log (\max x_i))O(nlog(maxxi))二分O ( log ( max x i ) ) O(\log (\max x_i))O(log(maxxi))轮每轮贪心验证O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)存储位置数组整数二分 贪心验证的核心思想单调性若距离d dd可行能放m mm头牛则所有≤ d \le d≤d的距离也可行若d dd不可行则所有 d dd的距离均不可行。满足二分条件贪心最优性对于固定的d dd从左到右尽可能早地放牛能为后续留下更多空间是验证d dd是否可行的最优策略最大化最小值的经典框架最大化最小距离/最小化最大距离类问题通常转化为二分 贪心验证适用于资源分配 间距约束类问题核心是利用单调性二分搜索并用贪心验证可行性【解题思路】【算法标签】#普及- #整数二分【代码详解】#includebits/stdc.husingnamespacestd;intn,m,l,r,mid;inta[100005];intmain(){cinnm;// 输入n和mfor(inti1;in;i){// 输入n个牛舍的位置cina[i];}sort(a1,an1);// 按照从小到大排列因为后面需要二分搜索la[1],ra[n];// 定义l和rwhile(lr){// 二分模板intcnt0;// 统计可选择的牛舍midl(r-l)/2;// 二分模板intlasta[1];// 定义待比较的牛舍初始从第1个牛舍开始比较for(inti2;in;i){// 往后遍历所有牛舍if(a[i]-lastmid){// 如果两个牛舍之间的距离大于等于mid即可以被选择cnt;// 统计数自增1lasta[i];}}// cout cnt cnt endl;if(cntm-1)rmid;elselmid1;}coutl-1endl;// 因为r先动所以最终输出应该是l-1l最后1试探失败所以需要l-1即为midreturn0;}【运行结果】5 3 1 2 8 4 9 3