题解：P11639 Line Game

Langke_Saonian · 2025-02-06 20:05:07 · 题解

题目链接：P11639 Line Game。

个人见解：

这道题的难度我估摸着有 50\% 来自题面理解。毕竟这道题无论是从代码还是思维来讲都不像绿的难度。当然只是个人意见，不作参考。

进入正题：

既然题目难理解，那就先从题目下手。

题目大意：

在一个长度为 m+1 的坐标轴上，你从坐标 1 开始，要进行多次操作。

操作内容是给出一些元素，你要删除他们。

删除有两种情况，分别为全部删除或部分删除。

删除元素遵循以下操作：

1. 选定一个值域 [L,R] ，在这个值域内的所有元素被删除，并付出相应代价，大小为 R-L+1 。

2. 若没有全部删除，则你的坐标 +1 ，你要在到达 m+2 （即出界）之前删除所有元素。

最后输出最小代价和。

题目简化：

多次给出一些元素，全部删除或部分删除，删除付出被删除元素的极差的代价，只能进行 m 次部分删除。求出删除所有元素的最小代价和。

题目分析：

题目中要求代价和最小，那么我们要尽可能的使代价被充分利用。因为代价与值域有关，而值域又与元素分布有关，我们要让元素分布集中，最好的方法就是将不集中的元素分成多个集中的部分，也就是部分删除。

因为部分删除只能使用 m 次，所以要尽可能减少不被利用的值域的长度。那我们可以用一个数组 e 来记录下给出的元素，排序后二次处理求差,再开一个 res 数组记录下来，这个过程就是计算出所有不被利用的值域。用 vector 记录方便又适合，是不二之选。

    vector<int> e;//记录每一条线段的元素 
    vector<int> res;//记录每条线段上相邻元素的差值 

计算答案可以使用整体减空白思想。即用每一组元素的极差之和（代码中最开始记为 ans ），减去被去除的值域的长度，最后得到答案。