贪心杂题

· · 个人记录

区间覆盖问题：

0.

在每个点都会被覆盖的情况下 都尽量往后放

易知没有更优的方案

1. 在一条数轴上有n个互不相交的区间，现在你需要画不超过m条线段，使得 所有的区间都被你画出的线段覆盖了。 你需要最小化线段的长度之和。

sol：写出线段长度发现就是左右边界减去m-1个缝隙长度之和。 • 因此对相邻两个区间的缝隙长度从大到小排个序，取前m-1大的从总长中 减去即可。 【正难则反】

1. 伟大的2320学长特别喜欢打地鼠游戏，这个游戏开始后，会在地 板上冒出一些地鼠来，你可以用榔头去敲击这些地鼠，每个地鼠 被敲击后，将会增加相应的游戏分值。可是，所有地鼠只会在地 上出现一段时间（而且消失后再也不会出现），每个地鼠都在0 时刻冒出，但停留的时间可能是不同的，而且每个地鼠被敲击后 增加的游戏分值也可能是不同。 • 最近2320学长经常玩这个游戏，以至于敲击每个地鼠只要1秒。 他在想如何敲击能使总分最大。

按时间顺序排序，不断取，如果地鼠数比当前时间大就pop掉最小的

因为维护了每个时间的答案，因而贪心正确

2.