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

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;
}