贪心 - 补集思想

2020-12-30 06:10:32

题目：ACwing 1349. 修理牛棚

题目来源：https://www.acwing.com/problem/content/1351/

描述：

在一个下着暴风雨的夜晚，大风掀翻了农夫约翰的牛棚的屋顶和大门。

牛棚一个个的并排排成一排，奶牛就住在牛棚中过夜。

由于一些奶牛正在外面度假，牛棚并没有住满，有的牛棚住着牛，有的牛棚空着。

所有的棚子的宽度都相同。

现在，约翰需要订购一批木板用来挡在牛棚的门口。

木材供应商将为他提供任意长度的木板，但是能够提供的木板数量非常有限。

约翰希望他购买的木板的总长度尽可能的小。

现在，给定可以购买的最大木板数量 M，牛棚的总数 S，牛的总数 C，以及 C 个住着牛的牛棚编号。

请你计算确保购买的木板的总长度尽可能小的情况下，为了使所有住着牛的牛棚都用木板挡住门，最少要将多少牛棚的门用木板挡住。

输入格式
第一行包含三个整数 M,S,C。

接下来 C 行，每行包含一个整数，表示一个住着牛的牛棚的编号。

输出格式
输出一个整数，表示被木板挡住门的牛棚的数量。

数据范围
$1≤M≤50,$
$1≤S≤200,$
$1≤C≤S,$
牛棚编号依次为 1∼S。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

输出样例：

1
25

样例解释
一种可行的方案是，用一个木板将 3∼8 号牛棚的门挡住，一个木板将 14∼21 号牛棚的门挡住，一个木板将 25∼31 号牛棚的门挡住，一个木板将 40∼43 号牛棚的门挡住，这样一共遮挡了 25 个牛棚的门。

算法1：$O(nlog n)$

题目大意：
给定m块木板长度随意，有一排牛棚，有些牛棚有牛有些没有。问在木板数量一定的时候，最少需要覆盖多少牛棚才能把有牛的牛棚给覆盖完。

思路:
这时候可以考虑一个补集的思想，首先用一整块木板使所有牛棚都覆盖掉 长度 = 终点 - 起点 + 1, 然后再对空牛棚的间隔长度进行从大到小排序。
有m块木板，最多可以去掉 m - 1个空牛棚间隙。去掉 m - 1个间隙后一定是在m块木板下总木板长度最短。

证明：
原问题的选法，对m块木板的长度选法一定一一对应选m - 1个区间。m - 1个区间的长度 + m 块木板的长度 = 总牛棚的数量。
总牛棚的数量不变，要想m块木板的长度最小，只用 m - 1个区间的长度最大即可。对没有牛棚的区间长度进行从大到小排序，依次选择前 m - 1个区间。

时间复杂度分析：
只用到了排序，所以时间复杂度$O(nlog n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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 个， 去掉m - 1段，就是m 块木板
    for(int i = 1; i <= m - 1 && i < c;  i++) res -= b[i];

    cout << res << endl;
    return 0;
}
  1. 1. 算法1：$O(nlog n)$