题目大意

把一个高速公路看作由连续排列的一个个格子组成，有n个格子上有坑。给出m，要求出m段区间，使得这m区间覆盖到所有坑（交通管制），且占据的格子数量最少。输出占据的格子数。

题解

换个角度看问题。因为正常通行的路段上没有坑，故想到原题相当于求m-1个没有坑的区间，求这些区间占据格子数的最大值。把两两坑间隔求出来，从大到小排序，选出前面m-1个间隔值，再有总区间长度减去它即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

#include <iostream>

using namespace std;

const int MAX_POS_CNT = 15010;

#define ll long long

ll Poss[MAX_POS_CNT], Delta[MAX_POS_CNT];

bool cmp(ll a, ll b)

{

	return a > b;

}

int main()

{

	ll n, m;

	ll ans = 0;

	scanf("%lld%lld", &n, &m);

	for (int i = 1; i <= n; i++)

		scanf("%lld", Poss + i);

	Poss[0] = Poss[1];

	for (int i = 1; i <= n; i++)

	{

		Delta[i] = Poss[i] - Poss[i - 1] - 1;

		ans += Poss[i] - Poss[i - 1];

	}

	ans++;

	sort(Delta + 1, Delta + n + 1, cmp);

	for (int i = 1; i <= m - 1; i++)

		ans = ans - Delta[i];

	cout << ans << endl;

}

巴特西

luogu2242 公路维修问题

题目大意

题解

最新文章

热门文章