USACO修理牛棚(贪心）

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

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

由于一些奶牛正在外面度假，牛棚并没有住满，有的牛棚住着牛，有的牛棚空着。
所有的棚子的宽度都相同。

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

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

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

现在，给定可以购买的最大木板数量 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∼17 号牛棚的门挡住，一个木板将21∼31号牛棚的门挡住，一个木板将 40∼43号牛棚的门挡住，这样一共遮挡了 25 个牛棚的门。

#include
using namespace std;
const int N=210;
int m,s,c;
int a[N];
struct node{int l,r;int sum;bool operator<(const node&a)const{return sum>a.sum;}
}t[N];
int main(){cin>>m>>s>>c;for(int i=1;i<=c;i++)cin>>a[i];sort(a+1,a+c+1);int k=0;for(int i=2;i<=c;i++){int b;b=a[i-1];t[k++]={b,a[i],a[i]-b-1};//相邻的点之间的没出现的牛棚数量}sort(t,t+k);int cnt=0;for(int i=0;i<m-1&&i<c-1;i++){cnt+=t[i].sum;}int ans=(a[c]-a[1]+1)-cnt;cout<<ans<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！