AcWing 1349. 修理牛棚
原题链接
中等
作者:
芝士雪豹我们走
,
2024-04-27 10:54:01
,
所有人可见
,
阅读 1
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
//贪心
using namespace std;
const int N = 210;
int m, s, c;
int a[N], b[N];
int main()
{
cin >> m >> s >> c;
for(int i = 0;i < c; i ++) cin >> a[i];//输入牛棚的编号
sort(a, a + c);//牛棚的编号排序
int res = a[c - 1] - a[0] + 1;//计算第一个牛棚到最后一个牛棚之间的长度
for(int i = 0;i + 1 < c;i ++) b[i] = a[i + 1] - a[i] - 1;//中间连续0的数量
sort(b, b + c - 1, greater<int>());//按照从打到小排序 一共包含c-1个区间
for(int i = 0;i < m - 1 && i < c - 1;i ++)//选最大的n-1个数
res -= b[i];//从数组中减去0的长度
cout << res << endl;//输出结果
return 0;
}