题解

本题使用贪心算法求解火柴分配的最小时长问题。

算法思路：

1. 问题建模：

   • 有 $n$ 个客人，分别在时刻 $t[1], t[2], \ldots, t[n]$ 到达
   • 有 $k$ 根火柴，每根火柴可以维持一段连续时间
   • 目标：最小化炉子运作的总时长

2. 基础时长：

   • 如果只用一根火柴，需要从第一个客人到达到最后一个客人离开
   • 基础时长：$ans = t[n] - t[1] + 1$
   • 加1是因为最后一个客人离开后才能关闭炉子

3. 间隔计算：

   • 计算相邻两个客人之间的无客时间间隔
   • $a[i] = t[i+1] - t[i] - 1$（共 $n-1$ 个间隔）
   • 这些间隔是可以通过分配火柴来"节省"的时间

4. 贪心策略：

   • 将所有间隔按从小到大排序
   • 选择最大的 $k-1$ 个间隔进行分割（因为 $k$ 根火柴产生 $k-1$ 个分割点）
   • 从答案中减去这些间隔的时长

5. 正确性证明：

   • 每选择一个间隔分割，相当于在该间隔内关闭炉子
   • 选择最大的间隔能最大化节省的时间
   • 贪心选择局部最优解即为全局最优解

时间复杂度：$O(n \log n)$，主要是排序的时间复杂度。

这是一道经典的区间覆盖贪心问题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, k, ans = 0; // ans记录炉子运作的总时长
int t[maxn], a[maxn]; // t存储客人前来时间，a存储无客人的间隔时间
int main() {
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &t[i]);
    }

    ans += t[n] - t[1] + 1; // 从头开到尾的时长(要到客人离开才可以关闭，所以需要+1)

    for (int i = 1; i < n; i++) {
        a[i] = t[i + 1] - t[i] - 1;
    }

    sort(a + 1, a + n); // 对无客间隔排序

    for (int i = n - 1; i >= n - k + 1; i--) { // 共n-1个间隔，共k根火柴
        ans -= a[i];
    }

    printf("%d", ans);
    return 0;
}