P1209 修理牛棚 Barn Repair 【洛谷算法习题】

P1209 修理牛棚 Barn Repair

网页链接

P1209 修理牛棚 Barn Repair

题目描述

在一个月黑风高的暴风雨夜，Farmer John 的牛棚的屋顶、门被吹飞了，好在许多牛正在度假，所以牛棚没有住满。

牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。有些牛棚里有牛，有些没有。所有的牛棚有相同的宽度。

自门遗失以后，Farmer John 必须尽快在牛棚之前竖立起新的木板。他的新木材供应商将会供应他任何他想要的长度，但是吝啬的供应商只能提供有限数目的木板。Farmer John 想将他购买的木板总长度减到最少。

给出m , s , c m,s,cm,s,c，表示木板最大的数目、牛棚的总数、牛的总数；以及每头牛所在牛棚的编号，请算出拦住所有有牛的牛棚所需木板的最小总长度。

输入格式

一行三个整数m , s , c m,s,cm,s,c，意义如题目描述。
接下来c cc行，每行包含一个整数，表示牛所占的牛棚的编号。

输出格式

输出一行一个整数，表示所需木板的最小总长度。

输入输出样例 #1

输入 #1

4 50 18 3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43

输出 #1

25

说明/提示

【数据范围】
对于100 % 100\%100%的数据，1 ≤ m ≤ 50 , 1 ≤ c ≤ s ≤ 200 1\le m \le 50,1\le c \le s \le 2001≤m≤50,1≤c≤s≤200。

USACO Training Section 1.3

解题思路

本题核心是贪心算法，求解用指定数量木板覆盖所有有牛牛棚的最小总长度。首先将有牛的牛棚编号升序排序，计算完整覆盖所有牛棚的基础总长度：最右侧牛棚 - 最左侧牛棚 + 1。若木板数量m大于等于牛的数量c，直接每头牛用一块木板，总长度为c。若木板不足，计算相邻牛棚之间的空隙长度，将空隙降序排序，优先在最大的 m-1 个空隙处分割木板，总长度减去这些最大空隙的和，即为最小总长度。该贪心策略能最大化节省木板长度，高效解决问题。

总结

核心逻辑：优先分割最大的空隙，用最少的木板长度覆盖所有有牛的牛棚。
关键操作：牛棚编号排序、计算相邻空隙、贪心选取最大空隙分割。
效率保障：排序+线性遍历，时间复杂度极低，完美适配题目数据范围。

代码内容

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){intm,s,c;cin>>m>>s>>c;vector<int>stalls(c);for(inti=0;i<c;++i){cin>>stalls[i];}// 牛棚编号排序sort(stalls.begin(),stalls.end());// 如果木板数量不少于牛的数量，每头牛单独一块木板if(c<=m){cout<<c<<endl;return0;}// 计算相邻牛棚之间的空隙（空牛棚的数量）vector<int>gaps;for(inti=1;i<c;++i){gaps.push_back(stalls[i]-stalls[i-1]-1);}// 空隙从小到大排序sort(gaps.begin(),gaps.end());// 初始总长度为 c（每头牛单独一块木板）// 需要合并的次数为 c - m，每次合并增加对应空隙的长度inttotal=c;intneed_merge=c-m;for(inti=0;i<need_merge;++i){total+=gaps[i];}cout<<total<<endl;return0;}