记录145#includebits/stdc.h using namespace std; const int N1e510; int a[N]; int main(){ int n0,m0; cinnm; for(int i1;in;i) cina[i]; sort(a1,an1); // 牛舍位置不一定有序必须先排序为后续贪心做准备 int ans0; int L1,Ra[n],mid0; // 二分答案最小距离的下界是1上界是最大坐标差 while(LR){ mid(LR)/2; // 贪心验证假设当前两头牛的最小距离为 mid最多能放几头牛 int cnt1; // 计数器第一头牛默认放在第一个牛舍 a[1] int ta[1]; // 记录上一头牛放置的位置 for(int i2;in;i){ // 如果当前牛舍与上一头牛的距离 mid说明可以放下一头牛 if(a[i]-tmid){ cnt; ta[i]; // 更新上一头牛的位置为当前牛舍 } } // 如果能放下的牛少于 m 头说明 mid 太大了需要减小距离 if(cntm) Rmid-1; else{ // 如果能放下 m 头或更多说明 mid 可行尝试更大的距离 ansmid; Lmid1; } } coutans; return 0; }题目传送门https://www.luogu.com.cn/problem/P1824前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的“最大值最小化”或最小值最大化问题通常使用二分答案 贪心验证的策略来解决。问题转化题目要求“最大化最近的两头牛之间的距离”。直接去求这个最大值非常困难因为组合情况太多。但如果我们反过来思考假设我们知道了两头牛之间的最小距离是 dd 我们能不能判断在这个距离下能不能放下 mm 头牛如果能放下说明 dd 是可行的我们可以尝试更大的距离如果放不下说明 dd 太大了需要减小距离。算法设计二分答案 贪心二分答案因为牛舍坐标在 [0,10^9]之间答案具有单调性如果距离 d 可行那么比 d 小的距离一定也可行。因此我们可以对“最小距离”进行二分查找。贪心验证Check函数在二分的过程中我们需要一个验证函数。为了在限定的最小距离 midmid 下尽可能多地放下牛我们采用贪心策略将牛舍排序后第一头牛永远放在第一个位置后续的牛只要与上一头牛的距离大于等于 mid 就立刻放下。这种策略能保证我们在不违反距离限制的前提下最紧凑地放置牛从而测试出当前 mid下最多能放多少头牛。代码分块详细解释1. 头文件、常量与数据预处理#includebits/stdc.h using namespace std; const int N1e510; int a[N]; int main(){ int n0,m0; cinnm; for(int i1;in;i) cina[i]; sort(a1,an1); // 牛舍位置不一定有序必须先排序为后续贪心做准备详细分析题目明确说明“不保证 x数组单调递增”。由于我们的贪心策略依赖于从左到右依次扫描牛舍因此必须首先对牛舍位置进行升序排序。sort(a1,an1)确保了数组的有序性这是后续二分和贪心正确执行的前提。2. 二分答案框架int ans0; int L1,Ra[n],mid0; // 二分答案最小距离的下界是1上界是最大坐标差 while(LR){ mid(LR)/2;详细分析这里对“最小距离”进行二分。下界 L1因为坐标是整数最小距离至少为1上界 Ra[n] 即最右端牛舍的坐标这是理论上的最大可能距离。mid代表我们当前正在验证的“假设最小距离”。3. 核心逻辑贪心验证Check过程// 贪心验证假设当前两头牛的最小距离为 mid最多能放几头牛 int cnt1; // 计数器第一头牛默认放在第一个牛舍 a[1] int ta[1]; // 记录上一头牛放置的位置 for(int i2;in;i){ // 如果当前牛舍与上一头牛的距离 mid说明可以放下一头牛 if(a[i]-tmid){ cnt; ta[i]; // 更新上一头牛的位置为当前牛舍 } }详细分析这是本题最核心的贪心策略。初始化为了让后面的牛有尽可能大的空间第一头牛必须放在最左边的牛舍a[1]。此时计数器cnt1上一头牛的位置t更新为a[1]。线性扫描从第二个牛舍开始遍历。对于每一个牛舍a[i]我们检查它与“上一头已经放下的牛”位置为t之间的距离。如果a[i] - t mid说明在这个牛舍放牛不会违反最小距离 mid 的限制。根据贪心思想我们立刻把牛放在这里并更新t为当前的a[i]。为什么贪心是正确的因为牛舍是排好序的如果当前牛舍a[i]可以放牛而我们选择跳过它去放更右边的牛舍只会让后续的牛空间变得更小或不变绝不会让能放下的牛更多。因此能放就放是最优策略。4. 二分区间的收缩与答案更新// 如果能放下的牛少于 m 头说明 mid 太大了需要减小距离 if(cntm) Rmid-1; else{ // 如果能放下 m 头或更多说明 mid 可行尝试更大的距离 ansmid; Lmid1; } } coutans; return 0; }详细分析不满足条件cnt m说明我们假设的最小距离 mid 太大了导致牛舍之间隔得太开连 mm 头牛都放不下。因此我们需要缩小距离将右边界 R 移动到 mid−1 。满足条件cnt m说明在最小距离为 mid 的情况下我们至少能放下 m 头牛。这是一个可行的解我们先用ans记录下这个 mid 。但是题目要求“最大化”这个距离所以 mid可能还不是最优的我们尝试增大距离将左边界 LL 移动到 mid1 继续寻找更大的可行解。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点数据预处理sort(a1,an1)将无序的牛舍坐标升序排列为后续从左到右的贪心扫描提供有序的基础环境二分框架L1, Ra[n]对“最小距离”进行二分查找将复杂的“求最大值”问题转化为简单的“验证可行性”问题贪心初始化cnt1, ta[1]默认第一头牛放在最左侧牛舍确立了贪心策略的起点为后续牛留出最大空间贪心验证if(a[i]-tmid)线性扫描能放牛就立刻放下在限定距离 midmid 下以最紧凑的方式测试最多能放多少头牛