首先如果木板的数量大于牛的总数 答案直接就是牛的总数了.
否则 我们一定会有一些木板覆盖空牛棚 我们想让木板总长度最小 就相当于覆盖尽可能少的空牛棚.
假设牛棚编号从左到右依次为1~S 我们把所有牛所在位置按编号从小到大排序 记录在**a[]**中.
PS: 本解法的变量命名同解法一.
我们不妨假设[a[1] a[c]]区间用一块木板覆盖了 但实际上我们可以用m块 我们可以想象成把一块木板分成了m块 相当于我们可以删除m - 1个gap. 因此我们贪心的删除最大的m - 1个gap即可.
需要注意的是 我们一共只有c - 1个gap 因此要么直接判断掉 m >= c的情况 否则应注意次数不应超过c - 1次.
当涉及到区间统计时 我们要定义好变量的含义 并注意是否需要±1.
vector gap;