题目描述
在一个下着暴风雨的夜晚,大风掀翻了农夫约翰的牛棚的屋顶和大门。
牛棚一个个的并排排成一排,奶牛就住在牛棚中过夜。
由于一些奶牛正在外面度假,牛棚并没有住满,有的牛棚住着牛,有的牛棚空着。
所有的棚子的宽度都相同。
现在,约翰需要订购一批木板用来挡在牛棚的门口。
木材供应商将为他提供任意长度的木板,但是能够提供的木板数量非常有限。
约翰希望他购买的木板的总长度尽可能的小。
现在,给定可以购买的最大木板数量 M,牛棚的总数 S,牛的总数 C,以及 C 个住着牛的牛棚编号。
请你计算确保购买的木板的总长度尽可能小的情况下,为了使所有住着牛的牛棚都用木板挡住门,最少要将多少牛棚的门用木板挡住。
样例
可能代码有点啰嗦,毕竟是自己才开始做题,不过个人感觉还很好理解
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int m, s, c;
cin >> m >> s >> c;
if(c <= m) // 如果有牛的牛棚个数小于可以购买的最大木板数量,直接返回牛棚个数就行了
{
cout << c << endl;
return 0;
}
vector<int> origin(c); // 记录原始输入数据
vector<vector<int>> vec(c, vector<int>(2)); // 仅仅用来排序前面每个vector的结构为{差,索引},差用来排序
for(int i = 0; i < c; ++i)
cin >> origin[i];
sort(origin.begin(), origin.end());
for(int i = 0; i < c - 1; ++i)
{
vec[i][0] = origin[i + 1] - origin[i]; // 计算差值
vec[i][1] = origin[i];
}
vec[c - 1][0] = -1; // 因为最后一个元素不重要了,但他的索引可能很大,因为我要差值大的前三个,所以-1
sort(vec.rbegin(), vec.rend()); // 降序排序,也可以自己写cmp 只需要 return a[0] > b[0];就可以
vector<int>disrupt(m - 1); // 记录三个断点,因为最多有m - 1个
for(int i = 0; i < disrupt.size(); ++i)
disrupt[i] = vec[i][1];
sort(disrupt.begin(),disrupt.end()); // 虽然记录了相差最大的,但是这里并不一定保证文件的输入是有序的,以防万一
int ans = 0, start = 0;
for(int i = 0, j = 0; i < c; ++i)
{
if(start == 0) start = origin[i];
if(j >= disrupt.size()) break;
if(origin[i] == disrupt[j])
{
ans += disrupt[j++] - start + 1;
start = 0;
}
}
ans += origin.back() - start + 1;
cout << ans << endl;
return 0;
}