题目描述
在一个下着暴风雨的夜晚,大风掀翻了农夫约翰的牛棚的屋顶和大门。
牛棚一个个的并排排成一排,奶牛就住在牛棚中过夜。
由于一些奶牛正在外面度假,牛棚并没有住满,有的牛棚住着牛,有的牛棚空着。
所有的棚子的宽度都相同。
现在,约翰需要订购一批木板用来挡在牛棚的门口。
木材供应商将为他提供任意长度的木板,但是能够提供的木板数量非常有限。
约翰希望他购买的木板的总长度尽可能的小。
现在,给定可以购买的最大木板数量 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 个牛棚的门。
算法
要保证木板的总长度尽可能小,理想状态是给每个有牛的牛棚配一块木板,但题目中限制了木板的数量。所以要满足将尽量少的牛棚用木板挡住,可以反过来思考,将尽量长的连续空牛棚优先去除,这就变成贪心问题了。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210;
int m, s, c;
int a[N], b[N];//a[]:有牛的牛棚编号,b[]:连续空牛棚的长度;
int main()
{
cin >> m >> s >> c;
for (int i = 0; i < c; ++i) cin >> a[i];//读入有牛的牛棚编号
sort (a, a + c);//从小到大排序
int res = a[c - 1] - a[0] + 1;//有牛牛棚的最长跨度(牛棚数量,包含空牛棚)
for (int i = 1; i < c; ++i) b[i] = a[i] - a[i - 1] - 1;//每段空牛棚的数量
sort (b + 1, b + c, greater<int>());//从大到小排序
for (int i = 1; i <= m - 1; ++i) res -= b[i];//优先排除尽量长的空牛棚区间,共排除m-1段
cout << res << endl;
return 0;
}
代码解析
a[c - 1] - a[0] + 1
计算第一个和最后一个有牛的牛棚区间共有多少个牛棚。b[i] = a[i] - a[i - 1] - 1
计算每段空牛棚的数量