企业官网建设流程全解析

不少人在OJ上刷题时，第一次遇到“东华OJ-基础题-49-修理牛棚”这道题，会被题目里一堆牛棚、木板、空隙绕晕。其实这道题的原型是USACO里的经典题 Barn Repair，后来被很多OJ收录为入门贪心题。它的核心就一句话：给你若干块木板，去盖住指定的牛棚，要求盖住的总长度最短。听起来很简单，但真上手写代码，很多人会卡在“到底怎么贪”和“边界条件怎么处理”上。这篇文章我就用C++完整拆解这道题，从读题到AC，把每一步的思路、代码、坑都讲清楚，适合刚学完排序和基础语法、准备开始刷贪心题目的新手。

1. 先别急着敲代码：把题目的数据关系彻底理清

1.1 题目到底给了你什么信息

题目给出的变量有三个：M、S、C。M是你能用的木板数量上限，S是这条牛棚的总数，C是实际有牛居住的牛棚数量。接下来会给你C个整数，每个整数代表一头牛所在的牛棚编号，编号范围在1到S之间。

有几个关键约束必须读懂：

• 木板数量最多是M块，没说必须用完，你可以用1块、2块，只要不超过M就行。
• 每块木板的长度不限，你可以买一块很长的板子盖住一整排，也可以买很多短木板分别盖住单个牛棚。
• 只有有牛的牛棚才需要被盖住，没有牛的牛棚理论上可以裸露。
• 但这里有个隐藏条件：如果一块木板同时盖住了两个有牛的牛棚，那么中间这段没有牛的区域也会被木板覆盖，这段长度同样计入总长度。这就是“浪费”的来源。
• 目标是让所有被木板覆盖的总长度最小。

换句话说，你要为所有有牛的牛棚“分配”木板，每块木板负责一段连续的区间，区间必须盖住至少一个有牛的牛棚，然后让所有区间长度的总和最小。

很多新手一开始想的是“从第一个有牛的牛棚到最后一个有牛的牛棚，总长度固定，然后怎么切”，这个方向其实已经接近答案了，只是不知道该怎么切、切多少刀。

1.2 手工推演一遍样例，比看十遍讲解都有用

我把这道题最典型的例子手写一遍，你跟着走一遍就明白贪心是怎么回事了。假设输入是：

3 20 5 1 3 8 10 20

M=3块木板，S=20个牛棚，C=5头牛，分别住在1、3、8、10、20号牛棚。

先看最笨的方案：用一块木板从1号牛棚盖到20号牛棚，长度是20-1+1=20。从1到20中间有几个空牛棚呢？2、4、5、6、7、9、11到19，这些全被木板盖住了，全算浪费。总覆盖长度是20。

现在你有3块木板，也就是可以在这块长木板上“砍两刀”，把它分成3段。每砍一刀，本质上就是“放弃覆盖某一段空隙”。我们来找所有可以砍的空隙：

• 1号牛棚和3号牛棚之间，空隙长度 = 3 - 1 - 1 = 1，也就是2号牛棚。
• 3号和8号之间，空隙长度 = 8 - 3 - 1 = 4，也就是4、5、6、7号。
• 8号和10号之间，空隙长度 = 10 - 8 - 1 = 1，也就是9号。
• 10号和20号之间，空隙长度 = 20 - 10 - 1 = 9，也就是11到19号。

四个空隙长度分别是1、4、1、9。你要砍两刀，当然要挑最长的两个砍，这样省下的覆盖长度最多。于是砍掉空隙9和4，剩下的覆盖区间是：

• 第1段：1号到3号，覆盖长度3（1、2、3，尽管2号没牛，但被盖住了）
• 第2段：8号到10号，覆盖长度3（8、9、10）
• 第3段：20号到20号，覆盖长度1

总长度 = 3 + 3 + 1 = 7。

如果用最开始的20减去砍掉的两个空隙9和4，得到20 - 9 - 4 = 7，结果完全一致。这就是核心思路：先把所有有牛的区域看成一整块，然后砍掉尽可能大的空隙。

2. 核心思路拆解：为什么“先整体覆盖，再砍掉大空隙”就是贪心

2.1 从一块长木板出发的逆向思考

正向思考这道题很麻烦，因为你不知道每块木板该放哪、多长。但逆向思考一下就清晰多了：假设你只有1块木板，那别无选择，只能从最左边的有牛牛棚盖到最右边的有牛牛棚，总长度固定。

现在让你多用一块木板，也就是从2块开始，你会怎么做？你一定会想：把原来那一整块木板在某处“剪断”，让这个断口正好落在某个空牛棚区域上，这样被剪掉的那段空牛棚就不用覆盖了，总长度减少。你当然希望减少得越多越好，所以会优先剪断最长的空隙。

这就是贪心策略的核心：每一步都选择当前最大的空隙进行切割。因为每增加一块木板，能减少的覆盖长度最多也就是某个空隙的长度，要想让最终总长度最小，必须优先处理最大的空隙。这个选择在每一步都是局部最优，而在这个问题里，局部最优恰好能推出全局最优。

为什么局部最优能推出全局最优？因为所有空隙是独立的——你砍掉空隙A，完全不影响空隙B的长度，也不会影响其他任何覆盖区间。每个空隙对最终总长度的“贡献”是线性的、互不干扰的，所以从大到小取前几个空隙就是最优解。

用一个生活化的类比：你买了一块很长的面包，上面有几段“空心的部分”，你要切几刀把空心部分去掉，每切一刀等于去掉一段空心，为了留下最多实心部分，你肯定先切最长的空心段。道理一模一样。

2.2 边界条件与特判：M大于C时的陷阱

这道题最容易WA的地方不是贪心过程，而是边界条件。

当M >= C时，你手里的木板比有牛的牛棚还多。这时候最聪明的做法是每个有牛的牛棚单独盖一块长度为1的木板，总长度就是C。比如C=5，有5头牛，你至少有5块木板，那就每个牛棚盖一块1米板，总覆盖长度=5。这个结论一定要在代码里单独判断，否则用上面的贪心逻辑会出问题。

还有一种边界情况是C=1，也就是只有一头牛。这时候不管M是多少，答案都是1，因为只需要一个长度1的木板盖住这一个牛棚。这个情况其实被M >= C这个特判覆盖了，因为C=1时M >= 1，直接输出1。

另外，牛的牛棚编号输入时是乱序的，必须先用sort排序，因为后面计算“最左和最右”以及“相邻空隙”都依赖有序数组。这个非常基础，但确实有人忘。

2.3 复杂度分析：为什么数组开200就够

题目给的S范围一般不超过200，C也不超过S。所以算法复杂度只要不是指数级，基本都能过。最常规的做法：

• 排序 O(C log C)，C最多200，几乎可以忽略。
• 计算空隙并排序 O(C log C)。
• 累加结果 O(M)，M最多50。

总复杂度非常低。所以这道题真正的难点不在性能，而在思路转换和边界处理。这也提醒我们，刷OJ题先看数据范围，很多基础题数据范围很小，暴力也能过，但我们要用更本质的贪心去做，这样以后遇到数据放大的版本才能直接迁移。

3. C++代码实现：从零到AC的完整过程

3.1 完整可提交的代码

下面这段代码我加了详细注释，直接提交到东华OJ就能过。我用的是最简的#include <bits/stdc++.h>，很多OJ支持，如果你用的编译器不支持，把它替换成需要的头文件即可。

#include <bits/stdc++.h> using namespace std; int main() { int M, S, C; // 东华OJ的题目可能有多组测试数据，用 while 循环读入最稳妥 while (cin >> M >> S >> C) { int stall[205] = {0}; // 存有牛的牛棚编号 for (int i = 0; i < C; i++) { cin >> stall[i]; } // 牛棚编号必须排序，后面所有计算都依赖有序数组 sort(stall, stall + C); // 特判：木板数量足够多时，每个有牛的牛棚单独盖一块长度为1的板 if (M >= C) { cout << C << endl; continue; } // 先用一块长木板覆盖最左到最右的牛棚 int total = stall[C - 1] - stall[0] + 1; // 计算所有相邻有牛牛棚之间的空隙长度 int gap[205] = {0}; for (int i = 0; i < C - 1; i++) { gap[i] = stall[i + 1] - stall[i] - 1; } // 空隙从大到小排序，因为我们想先砍掉最长的空隙 sort(gap, gap + C - 1, greater<int>()); // 最多有 M 块木板，意味着可以砍 M-1 刀 // 每砍一刀，就从 total 中减去一个空隙长度 for (int i = 0; i < M - 1; i++) { total -= gap[i]; } cout << total << endl; } return 0; }

3.2 关键代码逐行解读

先把几个最容易被忽略的细节展开讲。

while (cin >> M >> S >> C)这行。很多OJ的题面不会明确说“多组测试数据”，但实际评测时可能有多组。用这种写法，读到文件末尾自动结束，不会报错。这是OJ刷题的基本功。

sort(stall, stall + C)。因为数组是int类型，默认按从小到大排序。排序之后，stall[0]是最左边的有牛牛棚，stall[C-1]是最右边的有牛牛棚。

total = stall[C-1] - stall[0] + 1。这是“一整块木板方案”的总长度。注意一定要加1，因为这是闭区间。比如从1号盖到20号，长度是20-1+1=20，不是19。这个+1是最容易写漏的地方。

gap[i] = stall[i+1] - stall[i] - 1。这个计算的是中间空牛棚的个数。比如1号和3号之间，3-1-1=1，说明中间只有1个空牛棚，也就是2号。如果不减1，会把相邻两个有牛牛棚的“距离”当成空隙，那就错了。相邻的两个有牛牛棚，比如5号和6号，它们之间空隙是6-5-1=0，也就是没有空隙，这时无论怎么切，都省不下长度。

sort(gap, gap + C - 1, greater<int>())。这里用了STL的greater ()，作用是从大到小排序。如果你不熟悉这个写法，也可以先从小到大排，再从后往前取，但用greater ()最直观。

for (int i = 0; i < M - 1; i++)。M块木板最多需要M-1刀。比如M=3，最多砍2刀，也就是能省下2个空隙的长度。如果M=1，循环不执行，total就是整个区间的长度，符合直觉。注意这里不用判断i是否超过C-2，因为前面已经特判M >= C的情况，所以M-1一定小于C-1，循环不会越界。

3.3 提交前最后检查一遍的清单

写完后别急着提交，对着这份清单自查：

• 有没有处理M >= C的情况？很多WA都是因为这个。
• 排序了吗？没有排序，空隙计算全乱。
• total计算有没有加1？很多答案差1就是这里。
• gap计算有没有减1？同理。
• 数组开的是不是足够大？虽然S最大200，但我习惯开到205，留点余量。
• 如果用while(cin >> ...)处理多组数据，输出时有没有换行？cout << total << endl; 这行别忘。

把这几个点都检查完，基本就能过了。

4. 踩坑实录：这些问题我当年都遇到过

4.1 常见错误速查表

我在刷这道题以及帮助别人调试时，发现WA的原因非常集中。整理了一张表，直接对号入座：

这张表里最经典的组合就是：忘记特判M >= C，同时gap排序方向又搞反，导致答案完全不对。

4.2 本地测试的几组关键用例

光靠样例输入不够，我建议你在本地把下面几组极端数据都跑一遍，确认输出符合预期。

第一组：M=1，S=10，C=3，牛在2、5、8。因为只有1块木板，答案就是从2到8，长度是8-2+1=7。这个用例验证的是当M=1时，代码不会去切割任何空隙。

第二组：M=5，S=10，C=3，牛在2、5、8。M >= C，答案是3。验证特判是否正确，3头牛各盖一块长度1的木板。

第三组：M=2，S=10，C=3，牛在1、2、10。空隙只有1个，在2和10之间，长度是10-2-1=7。M=2时可以砍1刀，砍掉7，总长度=10-7=3。验证一下：两块木板分别盖1到2（长度2）和10（长度1），总长度3，正确。

第四组：M=2，S=10，C=2，牛在4、5。两头牛相邻，空隙为0。总长度=5-4+1=2，即使有2块木板也无缝可切，答案仍为2。这个用例很容易让人困惑，但其实是正确的，因为相邻牛棚之间的空隙是0。

4.3 一个隐藏的比较深的坑：空隙为0的情况

如果两个有牛的牛棚相邻，比如4号和5号，那么它们之间的空隙gap就是5-4-1=0。排序后，0会被排到最后。假设此时M很大，循环会取到一些值为0的空隙，total减去0，保持不变，这其实是正确的——因为两个相邻的有牛牛棚之间没有浪费，切不切都一样。

但如果你在计算时把gap写成stall[i+1] - stall[i]，没有减1，那么相邻牛棚之间的gap就是1，程序会误以为这里有空隙，于是砍掉这个“空隙”，总长度被错误地减了1。这就是为什么gap必须减1的核心原因。类似的，如果total忘记加1，也会出现偏差。这两个“1”是这道题最容易出错的细节，一定要在草稿纸上把闭区间长度的公式推到一遍。

5. 从这道题延伸出去：一类“砍断空隙”的贪心套路

5.1 相邻元素差值与排序的组合

修理牛棚这道题，本质上是“给你若干个点，用不超过M个区间覆盖它们，让区间总长度最小”。这类题有一个通用的处理套路：

第一步，把所有点排序。 第二步，计算相邻点之间的“空隙代价”。 第三步，从总数中减去若干最大的空隙。

这个三步走模板在算法题里用途很广。比如类似的“种树问题”、“修路问题”、“安排工作台”等变形题，很多都可以套用这个思路。区别只在于空隙的代价怎么算、最多能砍几刀。

以这道题为例，代价是相邻有牛牛棚之间的空牛棚数量，刀数是M-1。有的题目会改成“每块木板长度必须相同”、“木板有宽度”、“空隙必须大于某个值才能切”等限制，思路不变，只是选择标准和循环条件变了。

把模板记牢之后，遇到新题时先问自己三个问题：需要覆盖的“点”是什么？两个点之间的空隙代价怎么算？最多允许切几刀？想清楚这三个问题，代码结构基本就出来了。

5.2 从逆推角度理解贪心的本质

很多人学贪心时觉得“贪心就是每步取最大/最小”，但这样很容易在真正需要贪心策略的题目上翻车。修理牛棚这道题的价值在于，它能让你直观感受到“为什么每步取最大空隙，最终结果就是最优”。

一个更严谨的理解方式是：最终方案一定是把原区间切成了若干段。切掉的每一段都对应一个空隙，而切掉的空隙总长度 = 原区间总长度 - 最终覆盖长度。要让最终覆盖长度最小，就要让切掉的空隙总长度最大。在所有空隙中选若干个加起来最大，当然是从大到小选。这里的贪心成立不是因为“看起来合理”，而是因为目标函数是可以分解的：原区间长度固定，切掉哪些空隙之间没有相互影响，所以选最大的几个一定最优。

下次再遇到贪心题，不妨先尝试把“最终答案”表示成某个固定值减去若干可选项的和，如果这些可选项互不影响，那从大到小选就是显然的最优解。这个思考方式比背模板有用得多。

5.3 C++实现中的几个STL小技巧

这道题虽然简单，但涉及的C++知识点其实不少。sort是必考的。排序对象是原数组时用sort(arr, arr+n)，排序对象是vector时用sort(v.begin(), v.end())。从大到小排序可以用sort(..., greater ())，但要注意这个greater ()是STL里的函数对象模板，需要包含functional头文件，通常bits/stdc++.h已经包含了。

还有一点，很多人不知道可以给sort传自定义比较函数。比如这道题如果不想用greater ()，可以这样写：

bool cmp(int a, int b) { return a > b; } sort(gap, gap + C - 1, cmp);

两种写法效果一样，你习惯哪种用哪种。但作为刷题党，学会greater ()这种内置的写法能省不少事，因为它不需要额外写函数。

如果C的数据量更大，gap的开法也会讲究一些。现在C最大200，随便用静态数组。如果遇到C达到10^5的版本，直接把数组改成vector gap(C-1)就好，逻辑完全不变。这也是为什么我建议练习时就用静态数组把逻辑练熟，数据量大的时候迁移到vector非常顺滑。

6. 再次总结这道题带给我的三个收获

6.1 读题时先找“浪费在哪里”

任何涉及“覆盖区间”的题目，想清楚浪费在哪里，思路就打开了一半。修理牛棚的浪费在空隙，所以目标就是减少空隙。很多区间问题的浪费可能体现在重复覆盖、空闲时间、未使用的容量等，找到浪费点，就找到了优化的下手方向。

6.2 特判不是可有可无的补充

M >= C这个特判，很多人觉得“不就一个if嘛”，但正是这个if让无数WA出现。刷OJ的时候，边界条件永远要放在思考的最前面，而不是代码写完了再补。题目给出的M、S、C的关系，每一个极端情况都值得单独测一下。

6.3 把简单题吃透，比刷十道难题有用

说实话，这道题代码不到30行，难度也不大，但它把贪心的核心逻辑、排序的应用、边界处理、多组输入这些基本功全都考了一遍。如果你能把这道题的每行代码、每个公式、每个角落都讲给别人听，那你对贪心入门这块就已经很扎实了。我当年刷完这道题后，又把类似的区间覆盖题目做了几道，明显感觉思路通顺了很多。

最后分享一个我个人的刷题习惯：每次AC之后，不是马上看下一题，而是把这道题改成不同的数据范围重新做一遍。比如把S改成10^5，用vector重新写；把M改成很大，测试特判逻辑；把输入改成乱序，确认排序没漏。这样折腾一圈，这道题才是真正吃透了。修理牛棚这道题值得你这么做。