题目描述
在一个下着暴风雨的夜晚,大风掀翻了农夫约翰的牛棚的屋顶和大门。
牛棚一个个的并排排成一排,奶牛就住在牛棚中过夜。
由于一些奶牛正在外面度假,牛棚并没有住满,有的牛棚住着牛,有的牛棚空着。
所有的棚子的宽度都相同。
现在,约翰需要订购一批木板用来挡在牛棚的门口。
木材供应商将为他提供任意长度的木板,但是能够提供的木板数量非常有限。
约翰希望他购买的木板的总长度尽可能的小。
现在,给定可以购买的最大木板数量 M
,牛棚的总数 S
,牛的总数 C
,以及 C
个住着牛的牛棚编号。
请你计算确保购买的木板的总长度尽可能小的情况下,为了使所有住着牛的牛棚都用木板挡住门,最少要将多少牛棚的门用木板挡住。
贪心
找最短 = 找最长的无牛的牛棚(正难则反)
取最长的前m - 1个牛棚(贪心)
时间复杂度
$o(n)$
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N = 210;
int f[N];
priority_queue<int,vector<int>,less<int>> heap;
int m,s,c;
int main()
{
cin >> m >> s >> c;
for(int i = 0;i < c;i ++)cin >> f[i];
sort(f,f + c);
for(int i = 0;i < c - 1;i ++)heap.push(f[i + 1] - f[i] - 1);
int res = f[c - 1] - f[0] + 1;
for(int i = 0 ;i < m - 1 && heap.size();i ++)
{
int t = heap.top();
heap.pop();
res -= t;
}
cout << res;
}