题解

1. 把题目翻译成“区间覆盖”

题目要求：

$$x_i\le y_i$$

并且对于每个 $c_i$，至少存在一个 $j$，满足：

$$x_j\le c_i\le y_j$$

注意：

$$x_j\le c_i\le y_j$$

就等价于：

$$c_i\in[x_j,y_j]$$

所以每一对 $(x_j,y_j)$ 就可以看成一个区间：

$$[x_j,y_j]$$

题目实际上是在问：

用$k$ 个区间覆盖所有的 $c_i$，使这些区间长度之和最小。

2. 先把所有 $c_i$ 排序

假设排序后：

$$a_1\le a_2\le\cdots\le a_n$$

相同的数没有必要重复考虑，所以可以去重：

$$a_1<a_2<\cdots<a_m$$

例如：

原序列：
-5 0 10 4 0

排序：
-5 0 0 4 10

去重：
-5 0 4 10

---

3. 一个区间覆盖哪些数？

假设一个区间：

$$[x,y]$$

覆盖了 (a_l) 和 (a_r)。

因为：

$$a_l\le a_{l+1}\le\cdots\le a_r$$

所以中间所有数也一定满足：

$$x\le a_i\le y$$

也就是说：

一个区间覆盖排序后的数时，它覆盖的一定是一段连续的数。

例如：

-5   0   4   10
|---------|

如果覆盖 -5 和 4，那么 0 也必然被覆盖。

---

4. 一个区间覆盖一段数时，最优怎么取？

假设一个区间负责：

$$a_l,a_{l+1},\dots,a_r$$

那么必须有：

$$x\le a_l$$

以及：

$$y\ge a_r$$

我们要最小化：

$$y-x$$

所以显然应该让区间刚好贴住两边：

$$x=a_l,\qquad y=a_r$$

此时贡献：

$$y-x=a_r-a_l$$

因此：

覆盖一段数的最小代价，就是这一段最大值减最小值。

---

5. 分段

这是这题最重要的一步。

题目允许不同区间互相重叠，例如：

$$[1,5]$$

和

$$[4,10]$$

假设：

$$x_1\le x_2\le y_1\le y_2$$

两个区间为：

$$[x_1,y_1],\quad[x_2,y_2]$$

它们有重叠部分。

原来的代价：

$$(y_1-x_1)+(y_2-x_2)$$

把它们合并成：

$$[x_1,y_2]$$

代价：

$$y_2-x_1$$

两者之差：

$$(y_1-x_1)+(y_2-x_2)-(y_2-x_1) =y_1-x_2$$

因为：

$$x_2\le y_1$$

所以：

$$y_1-x_2\ge0$$

因此：

$$y_2-x_1 \le (y_1-x_1)+(y_2-x_2)$$

也就是说：

两个重叠区间合并之后，答案不会变差。

所以我们总能找到一个最优方案，使有效区间之间没有重叠。

于是排序后的：

$$a_1,a_2,\dots,a_m$$

就可以看成被分成若干连续段。

例如：

a1 a2 a3 | a4 a5 | a6 a7

每一段对应一个区间。

而且如果最后只用了少于 $k$ 个区间，多出来的区间可以取：

$$x=y$$

它的长度是 (0)，不会影响答案。

所以实际上是：

最多使用 $k$ 段。

---

6. 一个区间

如果只使用一个区间，那么它必须覆盖：

$$a_1,\dots,a_m$$

所以区间就是：

$$[a_1,a_m]$$

答案：

$$a_m-a_1$$

例如：

-5  0  4  10

一个区间：

[-5,10]

代价：

$$10-(-5)=15$$

---

7. 如果增加一个区间呢？

现在允许使用两个区间。

假设在：

$$a_i,\ a_{i+1}$$

之间切一刀：

a1 a2 ... ai | ai+1 ... am

那么两个区间的代价：

$$(a_i-a_1)+(a_m-a_{i+1})$$

原来一个区间的代价：

$$a_m-a_1$$

两者相差：

$$(a_m-a_1) - [(a_i-a_1)+(a_m-a_{i+1})]$$

整理：

$$=a_{i+1}-a_i$$

所以：

在 $a_i$ 和 $a_{i+1}$ 之间切一刀，可以节省 $a_{i+1}-a_i$。

---

8. 应该在哪里切？

我们有：

$$a_1<a_2<\cdots<a_m$$

相邻差分别是：

$$a_2-a_1,\quad a_3-a_2,\quad \dots,\quad a_m-a_{m-1}$$

如果允许使用 $k$ 个区间，就最多可以切：

$$k-1$$

刀。

每切一刀，就节省一个相邻差。

所以为了让最终答案最小，我们应该选择：

$$\boxed{\text{最大的 }k-1\text{ 个相邻差}}$$

---

9. 为什么选最大的？

假设所有相邻差为：

5  4  6

如果只能切一刀：

• 切 5，答案减少 5
• 切 4，答案减少 4
• 切 6，答案减少 6

当然应该选择 6。

所以就是：

$$\text{答案} = (a_m-a_1) - \text{最大的 }k-1\text{ 个相邻差之和}$$

如果不同的数只有 (m) 个，那么最多只能切 (m-1) 刀，因此实际切刀数为：

$$\min(k-1,m-1)$$

---

10

具体做法非常简单：

1. 读入所有 (c_i)。
2. 排序。
3. 扫一遍，跳过重复元素。
4. 计算相邻不同元素之间的差值。
5. 将这些差值从大到小排序。
6. 初始答案为最大值减最小值。
7. 减去最大的 (k-1) 个差值。
8. 如果不同元素数量不足 (k)，就全部切掉。