AcWing 1349. 修理牛棚——贪心+暴力
原题链接
中等
作者:
春江花月夜ovo
,
2024-04-11 22:14:32
,
所有人可见
,
阅读 23
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
int m, s, c;
const int N = 210;
int a[N];
int ca[N];
bool st[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin >> m >> s >> c;
for (int i = 1; i <= c; i ++) cin >> a[i];
sort(a + 1, a + c + 1);
for (int i = 2; i <= c; i ++)
{
ca[i - 1] = a[i] - a[i - 1];
}
sort(ca + 1, ca + c, greater<int>());
int ans = a[c] - a[1] + 1;
for (int len = 0; len < m && len < c; len ++)
{
memset(st, false, sizeof st);
int cnt = 0;
for (int k = 1; k <= len; k ++)
{
for (int i = 2; i <= c; i ++)
{
if (a[i] - a[i - 1] == ca[k] && st[i] == false)
{
st[i] = true;
break;
}
}
}
int last = 1;
int bz = 0;
for (int i = 2; i <= c; i ++)
{
if (st[i])
{
cnt = cnt + a[i - 1] - a[last] + 1;
last = i;
bz ++;
}
if (i == c)
{
cnt = cnt + a[i] - a[last] + 1;
}
}
ans = min(ans, cnt);
}
cout << ans << "\n";
return 0;
}