P1209 [USACO1.3] 修理牛棚 Barn Repair 题解复盘模块贪心算法目标使用最多 M 块木板覆盖所有有牛的牛棚使木板总长度最小基本信息项目内容题目编号、来源P1209 洛谷 / [USACO1.3] Barn Repair 修理牛棚训练层级B 贪心变式题知识版块贪心、排序、区间分割、最大间隔解题前 · 关键信号识别维度分析目标、约束、底层结构目标使用不超过 M 块木板覆盖所有有牛的牛棚并使木板总长度最小。约束木板数量有限可以将连续区域分割成多个部分。底层结构先覆盖所有牛所在的范围再通过切割较大的空隙减少木板长度。数据规模c≤200数据规模较小排序 O(nlogn) 可以满足要求。候选算法和依据算法贪心 排序。依据木板数量为 M 时可以产生 M-1 个分割位置因此应该去掉最大的 M-1 个空隙使覆盖长度最小。复杂度预判排序牛棚位置 O(nlogn)排序空隙 O(nlogn)。总时间复杂度 O(nlogn)空间复杂度 O(n)。解题后 · 外化复盘维度内容实现结构 / 核心思路1. 将所有有牛的牛棚编号存入数组。2. 对牛棚编号排序找到最左和最右牛棚。3. 初始长度为a[c]-a[1]1表示覆盖所有牛需要的长度。4. 计算相邻牛棚之间的空隙a[i]-a[i-1]-1。5. 将空隙从大到小排序减去最大的m-1个空隙得到最小木板长度。错因回溯1. 容易认为应该连续覆盖所有牛棚没有考虑中间没有牛的位置可以省去。2. 容易忘记 M 块木板只能产生 M-1 个断点。3. 空隙计算错误应该是a[i]-a[i-1]-1不是简单的距离差。边界和易错点1. 当mc时每头牛可以单独使用一块木板答案为 c。2. 木板数量对应减少的空隙数量为m-1。3. 初始覆盖长度需要加 1。4. 空隙需要按照从大到小排序。下次看到什么信号我应该想到这个方法看到① 区间覆盖② 可以分成有限段③ 希望减少覆盖长度想到排序找最大空隙去掉最大的几个浪费部分。AC 完整代码#includeiostream#includealgorithm#includevectorusingnamespacestd;intmain(){intm,s,c;cinmsc;inta[205];intb[205]{0};for(inti1;ic;i){cina[i];}sort(a1,a1c);for(inti2;ic;i){b[i]a[i]-a[i-1]-1;}sort(b1,bc1,greaterint());intansa[c]-a[1]1;for(inti1;im;i){ans-b[i];}coutans;return0;}