题目描述

塔子哥接到一个新课题，监测一整条河流的水质。

目前塔子哥选择了一条河流进行水质监测，长度为 $N$ 公里。经过专业人员勘察，河流沿线有 $K$ 个候选地点适合安装水质监测站，每个监测站可以覆盖的长度为半径 $R$ 公里，单个监测站建设成本为 $M$ 。

题面描述

塔子哥接到一项任务，需要在一条长为 $N$ 公里的河流上监测水质。河流沿线有 $K$ 个候选地点适合建设水质监测站，每个监测站的覆盖半径为 $R$ 公里，建设一个监测站的成本为 $M$。任务是计算出最少需要多少经费才能覆盖整条河流，如果无法通过在所有候选地点建设监测站来实现覆盖，则输出 "-1"。输入包括河流长度、覆盖半径、建设成本以及候选地点的具体位置，输出则是最少经费或 "-1"。

思路

区间覆盖模板题目，这道题和区间覆盖的区别在于区间固定，我们使用贪心去解决对应的问题。

对于地址$i$，假设地址小于$i$的都已经被覆盖，那么如果我们需要覆盖它，我们可以选择的基站位置在范围$[i-R,i+R]$内。假设现在存在两个基站$x$和$y$$(y>x)$都满足对应的要求，那么我们更偏向于选择$y$基站，因为$y>x$，这样$y$的基站可以比$x$基站覆盖更多后面的地址。