AcWing 1349. 提供一个 y 总标准程序 修理牛棚
原题链接
中等
作者:
hairrrrr
,
2021-04-04 21:51:06
,
所有人可见
,
阅读 703
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 210;
int m, s, c;
int cows[N], spaces[N];
int main(void)
{
scanf("%d%d%d", &m, &s, &c);
for(int i = 0; i < c; ++i)
scanf("%d", &cows[i]);
sort(cows, cows + c);
// all 是牛棚的最大长度,注意需要加 1
int all = cows[c - 1] - cows[0] + 1;
for(int i = 1; i < c; ++i)
// 空隙需要减去 1
spaces[i] = max(0, cows[i] - cows[i - 1] - 1);
sort(spaces + 1, spaces + c, greater<int>());
// 注意这里是 m - 1,因为我们已经用掉了 1 块板子(覆盖所有有牛的牛棚)
for(int i = 1; i <= m - 1 && i < c; ++i)
{
all -= spaces[i];
}
printf("%d\n", all);
return 0;
}