贪心算法（算法竞赛、蓝桥杯）--修理牛棚

1、B站视频链接：A27 贪心算法 P1209 [USACO1.3] 修理牛棚_哔哩哔哩_bilibili

题目链接：[USACO1.3] 修理牛棚 Barn Repair - 洛谷

 

#include <bits/stdc++.h> 
using namespace std;
const int N=205;
int m,s,c,ans;
int a[N];//牛的位置标号
int d[N];//相邻牛之间的牛棚空挡数

int main(){
	scanf("%d%d%d",&m,&s,&c);
	for(int i=1;i<=c;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+c);
	for(int i=2;i<=c;i++)d[i-1]=a[i]-a[i-1]-1;
	sort(d+1,d+c);//注意是从2开始所以不用加一 
	
	ans=c;//先给每头牛一块木板 
	if(m<c){
		for(int i=1;i<=c-m;i++)ans+=d[i];//加空挡 
	}
	printf("%d\n",ans);
	return 0;
}