题解：洛谷 P1209 [USACO1.3] 修理牛棚 Barn Repair

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1209 [USACO1.3] 修理牛棚 Barn Repair - 洛谷【题目描述】在一个月黑风高的暴风雨夜Farmer John 的牛棚的屋顶、门被吹飞了 好在许多牛正在度假所以牛棚没有住满。牛棚一个紧挨着另一个被排成一行牛就住在里面过夜。有些牛棚里有牛有些没有。所有的牛棚有相同的宽度。自门遗失以后Farmer John 必须尽快在牛棚之前竖立起新的木板。他的新木材供应商将会供应他任何他想要的长度但是吝啬的供应商只能提供有限数目的木板。Farmer John 想将他购买的木板总长度减到最少。给出m,s,c表示木板最大的数目、牛棚的总数、牛的总数以及每头牛所在牛棚的编号请算出拦住所有有牛的牛棚所需木板的最小总长度。【输入】一行三个整数m,s,c意义如题目描述。接下来c行每行包含一个整数表示牛所占的牛棚的编号。【输出】输出一行一个整数表示所需木板的最小总长度。【输入样例】4 50 18 3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43【输出样例】25【核心思想】问题分析给定m mm块木板、s ss个牛棚、c cc头牛的位置要求用不超过m mm块木板覆盖所有有牛的牛棚使木板总长度最小。木板覆盖的是连续区间多块木板覆盖的区间不能重叠。这是一个贪心 区间分割问题关键在于利用空隙来减少木板数量。算法选择排序定位将牛的位置按编号排序得到连续覆盖所有牛所需的最小区间[ a 1 , a c ] [a_1, a_c][a1​,ac​]空隙分析相邻牛之间的空牛棚数d i a i 1 − a i − 1 d_i a_{i1} - a_i - 1di​ai1​−ai​−1是可节省的长度——如果在此处断开木板可以跳过这些空牛棚贪心选最大空隙木板数从1 11块增加到m mm块意味着可以断开m − 1 m-1m−1次。每次断开应选择最大的空隙以最大化节省的总长度等价转化最小总长度 全覆盖长度− -−最大的m − 1 m-1m−1个空隙之和关键步骤读入数据m , s , c m, s, cm,s,c和c cc个牛棚编号a [ 1.. c ] a[1..c]a[1..c]特判若m ≥ c m \geq cm≥c每头牛单独一块木板答案为c cc排序将牛棚编号从小到大排序计算空隙遍历i ii从2 22到c ccd i − 1 a i − a i − 1 − 1 d_{i-1} a_i - a_{i-1} - 1di−1​ai​−ai−1​−1贪心选取将空隙数组从大到小排序取前m − 1 m-1m−1个最大空隙计算答案ans ( a c − a 1 1 ) − ∑ i 1 m − 1 d i \text{ans} (a_c - a_1 1) - \sum_{i1}^{m-1} d_ians(ac​−a1​1)−∑i1m−1​di​时间/空间复杂度时间复杂度O ( c log ⁡ c ) O(c \log c)O(clogc)排序主导空间复杂度O ( c ) O(c)O(c)存储牛棚位置和空隙数组贪心分割的核心思想全覆盖为基准先用一块木板覆盖所有牛长度为a c − a 1 1 a_c - a_1 1ac​−a1​1空隙即节省在相邻牛群之间的空隙处断开木板可以跳过空牛棚减少总长度优先大空隙断开位置应选择最大的空隙因为每多一块木板只能减少一个断点必须让每次断开都产生最大效益木板数与断点数关系m mm块木板需要m − 1 m-1m−1个断点因此取最大的m − 1 m-1m−1个空隙适用于区间覆盖、资源分割、最小化连续段总长度等问题【解题思路】【算法标签】#普及 #贪心【代码详解】// 使用dfs算法最后2个测试点TLE#includebits/stdc.husingnamespacestd;// 全局变量定义intm;// 木板数量ints;// 牛棚总长度未使用intc;// 有牛的牛棚数量inta[205];// 存储有牛的牛棚编号intb[205];// 存储当前分配的木板覆盖的牛棚数intminn1e9;// 最小木板总长度初始化为极大值/** * 深度优先搜索函数用于尝试所有可能的木板分配方案 * param step 当前处理到第几块木板 */voiddfs(intstep){// 计算当前已分配的牛棚总数intsum0;for(inti1;im;i){sumb[i];}// 剪枝如果已超过总牛棚数则返回if(sumc){return;}// 当所有木板都分配完毕时if(stepm){// 检查是否正好覆盖所有牛棚if(sumc){intans0;// 当前方案的总木板长度intlast1;// 上一个牛棚的起始位置// 计算当前分配方案的总长度for(inti1;im;i){// 计算第i块木板的长度ans(a[lastb[i]-1]-a[last]1);// 剪枝如果已经超过当前最小值则提前返回if(ans(a[c]-a[1]1)){return;}// 更新下一块木板的起始位置lastlastb[i];}// 更新最小总长度minnmin(minn,ans);}return;}// 尝试为当前木板分配不同数量的牛棚for(inti1;ic-m;i){b[step]i;// 尝试分配i个牛棚给当前木板dfs(step1);// 递归处理下一块木板b[step]0;// 回溯重置分配}}intmain(){// 输入数据cinmsc;for(inti1;ic;i){cina[i];}// 将牛棚编号排序sort(a1,ac1);// 特殊情况处理if(m1){// 只有一块木板时必须覆盖所有牛棚couta[c]-a[1]1endl;exit(0);}if(mc){// 木板数多于牛棚数时每个牛棚单独一块木板coutcendl;exit(0);}// 开始深度优先搜索dfs(1);// 输出最小总长度coutminnendl;return0;}// 使用贪心重做一遍#includebits/stdc.husingnamespacestd;intm,s,c,a[205],b[205];boolcmp(intx,inty){returnxy;}intmain(){cinmsc;// 输入m、s和cs没有用for(inti1;ic;i){// 输入牛的位置cina[i];}if(mc){// 如果木板数大于牛的数量coutcendl;// 那么每头牛都可以有一块木板输出c并退出程序return0;}sort(a1,ac1);// 对a按照从小到大方式排序intmark1;// 定义b数组的下标for(inti2;ic;i){// 从第2头牛所在的牛棚开始遍历if(a[i]-a[i-1]1){// 如果两头牛之间有间隙b[mark]a[i]-a[i-1]-1;// 计算空隙}}sort(b1,bmark,cmp);// 对间隙按照从大到小方式排序intlena[c]-a[1]1;// 算出整个板的长度for(inti1;im-1;i){// 用总长度减去每个空隙的长度这里最多m-1个空隙减少1个空隙就需要2块木板减少2个空隙就需要3块木板...lenlen-b[i];}coutlenendl;// 输出最后的长度就是多块木板的总长return0;}#includebits/stdc.husingnamespacestd;intm,s,c,ans;// m: 木板数, s: 牛棚总数, c: 牛的数量inta[205];// 牛所占的牛棚的编号intd[205];// 相邻牛之间的空牛棚数intmain(){cinmsc;// 输入木板数, 牛棚总数, 牛的数量for(inti1;ic;i)// 输入每头牛所在的牛棚编号{cina[i];}sort(a1,ac1);// 按牛棚编号排序for(inti2;ic;i)// 计算相邻牛之间的空牛棚数{d[i-1]a[i]-a[i-1]-1;// 两牛之间的空牛棚}sort(d1,dc);// 对空牛棚数排序ansc;// 初始至少需要c块木板每头牛一块if(mc)// 如果木板数少于牛数{for(inti1;ic-m;i)// 需要合并c-m个间隔{ansd[i];// 加上间隔中的空牛棚}}coutans;// 输出最小木板总长度return0;}【运行结果】4 50 18 3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43 25