题目描述
给定m块木板长度随意,有一排牛棚,有些牛棚有牛有些没有。问在木板数量一定的时候,最少需要覆盖多少牛棚才能把有牛的牛棚给覆盖完。
思路:
这时候可以考虑一个补集的思想,首先用一整块木板使所有牛棚都覆盖掉 长度 = 终点 - 起点 + 1
, 然后再对空牛棚的间隔长度
进行从大到小排序。
有m块木板,最多可以去掉 m - 1
个空牛棚间隙。去掉 m - 1
个间隙后一定是在m块木板下总木板长度最短。
证明:
原问题的选法,对m块木板的长度选法一定一一对应选m - 1个区间。m - 1个区间的长度 + m 块木板的长度 = 总牛棚的数量
。
总牛棚的数量不变,要想m块木板的长度最小,只用 m - 1个区间的长度
最大即可。对没有牛棚的区间长度进行从大到小排序,依次选择前 m - 1个区间。
时间复杂度分析:
只用到了排序,所以时间复杂度$O(nlog n)$
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210;
int a[N], b[N]; // a 表示有牛牛棚的编号, b表示没有牛的牛棚的间隔长度
int m, s, c;
int main()
{
cin >> m >> s >> c;
for(int i = 0; i < c; i++) cin >> a[i];
sort(a, a + c);
// 一共是 c - 1 个间隔
for(int i = 1; i < c; i++) b[i] = a[i] - a[i - 1] - 1; // 7 8 9 中间8没有牛所以 9 - 7 - 1,间隔为1
sort(b + 1, b + c, greater<int>()); // 实现以从大到小排序
int res = a[c - 1] - a[0] + 1;
// 最多去掉m - 1个间隔,间隔数量不能超过 c - 1 个
for(int i = 1; i <= m - 1 && i < c; i++) res -= b[i];
cout << res << endl;
return 0;
}