【AcWing】蓝桥杯集训每日一题Day32|贪心|1349.修理牛棚

1349.修理牛棚

题目内容

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

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

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

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

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

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

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

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

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

输入格式

第一行包含三个整数 M,S,C。

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

输出格式

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

数据范围

1≤M≤50,

1≤S≤200,

1≤C≤S,

牛棚编号依次为 1∼S。

输入样例：

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

输出样例：

25

样例解释

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

题目解析

牛棚排成一排

有的牛棚住着牛，有的牛棚没有住着牛

牛棚的宽度都相同

木板的长度可以任意，木板的数量是有限的

希望订购木板的总长度最小

挡住所有有牛的牛棚，总木板数量不超过M的情况下，要购买的木板的总长度是多少

用1表示有牛，0表示没有牛

110100111，M=2

第一个木板挡前四个，第二个木板挡后三个，这样长度为7

第一个木板挡前二个，第二个木板挡后六个，这样长度为8

不同的方案，木板的长度是不一样的

希望找到一个总长度最小的方案

数据范围很小

用哪些线段把所有的1覆盖住

不如倒着想

从第一头牛到最后一头牛，先用一块板子都覆盖住

然后再挖空

把中间连续的0挖掉，这样最终也可以形成一些线段

先考虑一下这两种方案是不是等价的

显然等价

任意给一个正着做的方案，倒着做仍然可以得到

先一整个都覆盖住，再把中间的空挖掉，长度一样

对于任何一个倒着做的方案，先覆盖住，然后挖掉

正着做仍然可以得到，一个一个覆盖就可以了，长度也一样

求原题的最小值相当于求倒着做的最小值

中间有一些连续的0

挖空的时候，如果挖掉了连续0里面的某些0，在最优解中一定会把区间里面连续的0都挖掉

连续的0要么都不挖，要么都挖

先把其中连续的0都找出来

每一段都可以选择挖

倒着做的话，一开始只有一个区间，最多是有M个区间，每挖掉一段都会多一个区间，因此最多只能挖M-1个区间

一开始一整段长度是固定的，为了让剩下的总长度最小，应该让挖掉的总长度最大

先把所有可以挖的区间找出来

把长度丢到一个集合当中，在其中最多选择M-1个数，是的总和最大

按照从大到小排个序，取前M-1个最大的数，就可以了

经典贪心问题

先求一下第一个1到最后一个1的总长度

再把其中所有连续0的长度拿出来，扔到一个集合里

从大到小排序，取前最大的M-1个数，算一下总和，从总长度中减去，就是答案

代码

#include 
#include 
#include 
using namespace std;
const int N = 210;
int m, s, c;
int a[N], b[N];
//a表示初始牛所在的牛棚的编号，b表示每一段0的长度
int main()
{
	cin >> m >> s >> c;
	//读入所有牛的编号
	for (int i = 0; i > a[i];
	//先把牛的编号从小到大排个序
	sort(a, a + c);
	//计算一下从第一个1到最后一个1的长度
	int res = a[c - 1] - a[0] + 1;
	//再找到所有连续的0
	for (int i = 0; i + 1 

手机扫描二维码访问