为了更好的阅读体检，可以查看我的算法学习博客
在线评测链接:P1294
题目描述
塔子哥接到一个新课题，监测一整条河流的水质。
目前塔子哥选择了一条河流进行水质监测，长度为 N N N 公里。经过专业人员勘察，河流沿线有 K K K 个候选地点适合安装水质监测站，每个监测站可以覆盖的长度为半径 R R R 公里，单个监测站建设成本为 M M M 。
假设塔子哥知道的河流是一条直线，请计算最少需要多少经费建设水质监测站才能完成对整条河流(也就是直线上的每一个实数点)的水质监测。
输入描述
输入第一行包含三个整数
N
N
N ,
R
R
R ,
M
M
M .(
1
≤
N
≤
3000
,
10
≤
R
≤
200
,
1
≤
M
≤
100000
1 \leq N \leq 3000,10 \leq R \leq 200,1 \leq M \leq 100000
1≤N≤3000,10≤R≤200,1≤M≤100000 )
输入第二行包含
K
K
K 个整数
a
1
,
a
2
…
a
K
a_1,a_2…a_K
a1,a2…aK ,表示在高铁沿线的第
a
1
，
a
2
…
a
K
a_1，a_2…a_K
a1，a2…aK 公里的地点可以建设基站.(
1
≤
K
≤
N
,
0
≤
a
i
≤
N
1 \leq K \leq N,0 \leq a_i \leq N
1≤K≤N,0≤ai≤N )
输出描述
输出一个整数，表示最少花费的经费，如果所有候选地点均建设了基站还是无法覆盖则输出 “ − 1 -1 −1” 。
样例
输入
100 20 114514
10 30 50
输出
-1
样例2
输入
80 50 114514
0 20 40 60
输出
114514
思路
区间覆盖模板题目，这道题和区间覆盖的区别在于区间固定，我们使用贪心去解决对应的问题。
对于地址 i i i，假设地址小于 i i i的都已经被覆盖，那么如果我们需要覆盖它，我们可以选择的基站位置在范围 [ i − R , i + R ] [i-R,i+R] [i−R,i+R]内。假设现在存在两个基站 x x x和 y y y ( y > x ) (y>x) (y>x)都满足对应的要求，那么我们更偏向于选择 y y y基站，因为 y > x y>x y>x，这样 y y y的基站可以比 x x x基站覆盖更多后面的地址。
因此，我们对于每一个地址 i i i，我们都要进行 f o r j = m i n ( N , i + R ) t o i − R + 1 ， j − = 1 for~~ j = min(N, i+R)~~ to~~~ i-R+1，j-=1 for j=min(N,i+R) to i−R+1，j−=1的循环（这里枚举到 i − R + 1 i-R+1 i−R+1，而不枚举到 i − R i-R i−R的原因在于一旦选择 i − R i-R i−R这个基站，那么肯定存在大于 j j j的部分实数地址无法被覆盖），从 m i n ( N , i + R ) min(N,i+R) min(N,i+R)开始找基站，一旦找到就调用对应的基站。调用基站 j j j后，那么我们范围 [ j − R , j + R ] [j-R,j+R] [j−R,j+R]的所有地址都会被覆盖，因此，下一次我们需要枚举的地址应该从 j + R j+R j+R开始（不是 j + R + 1 j+R+1 j+R+1，因为我们需要保证所有实数地址被覆盖，而不是所有整数地址被覆盖）。
类似题目推荐
见知识点专栏-贪心
代码
CPP
#include <bits/stdc++.h>
using namespace std;
int N, R, M;
int arr[3005];
int main(){
cin >> N >> R >> M;
int num;
while(cin >> num){
arr[num] = 1;
}//输入
int ans = 0;
for(int i = 0; i <= N; i++){//枚举所有地址
bool f = false;
for(int j = min(N, i + R); j >= i - R + 1; j--){//找对应的基站
if(arr[j] == 1){
ans += M;
i = j + R - 1;//下一次我们需要枚举的地址为j+R
if(i + 1 == N){//特例，因为我们不需要覆盖大于N的部分实数地址，所以只要覆盖到N即可
cout << ans << endl;
return 0;
}
f = true;//一旦找到就记录，并且推出循环。
break;
}
}
if(!f){//没找到输出-1
cout << -1 << endl;
return 0;
}
}
cout << ans << endl;
return 0;
}
python_103">python
python">N, R, M = map(int, input().split())
arr = [0] * 3005
line = [int(i) for i in input().split()]#输入
for i in line:
arr[i] = 1
ans = 0
i = 0
while i <= N:#枚举所有地址
f = False
for j in range(min(i + R, N), i - R, -1):#找对应的基站
if arr[j] == 1:
ans += M
i = j + R - 1#下一次我们需要枚举的地址为j+R
if i + 1 == N:#特例，因为我们不需要覆盖大于N的部分实数地址，所以只要覆盖到N即可
print(ans)
exit(0)
f = True#一旦找到就记录，并且推出循环。
break
if not f:#没找到输出-1
print(-1)
exit(0)
i += 1
print(ans)
Java
java">import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int R = scanner.nextInt();
int M = scanner.nextInt();//输入
int[] arr = new int[3005];
for (int i = 0; i < 3005; i++) {
arr[i] = 0;
}
int num;
while(scanner.hasNext()){
num = scanner.nextInt();
arr[num] = 1;
}
int ans = 0;
int i = 0;
while (i <= N) {//枚举所有地址
boolean f = false;
for (int j = Math.min(i + R, N); j >= i - R + 1; j--) {//找对应的基站
if (arr[j] == 1) {
ans += M;
i = j + R - 1;//下一次我们需要枚举的地址为j+R
if (i + 1 == N) {//特例，因为我们不需要覆盖大于N的部分实数地址，所以只要覆盖到N即可
System.out.println(ans);
System.exit(0);
}
f = true;//一旦找到就记录，并且退出循环。
break;
}
}
if (!f) {//没找到输出-1
System.out.println(-1);
System.exit(0);
}
i++;
}
System.out.println(ans);
}
}
Go
package main
import (
"fmt"
)
func main() {
var N, R, M int
fmt.Scan(&N, &R, &M)
arr := make([]int, 3005)//输入
var num int
for {
_, err := fmt.Scan(&num)
if err != nil {
break
}
arr[num] = 1
}
ans := 0
i := 0
for i <= N {//枚举所有地址
f := false
for j := min(N, i+R); j >= i - R + 1; j-- {//找对应的基站
if arr[j] == 1 {
ans += M
i = j + R - 1//下一次我们需要枚举的地址为j+R
if i+1 == N {//特例，因为我们不需要覆盖大于N的部分实数地址，所以只要覆盖到N即可
fmt.Println(ans)
return
}
f = true//一旦找到就记录，并且退出循环。
break
}
}
if !f {//没找到输出-1
fmt.Println(-1)
return
}
i++
}
fmt.Println(ans)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Js
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let N, R, M;
let arr = new Array(3005).fill(0);
rl.question('', (line1) => {
const input1 = line1.trim().split(' ').map(Number);
N = input1[0];
R = input1[1];
M = input1[2];
rl.question('', (line2) => {
const input2 = line2.trim().split(' ').map(Number);
for (let i = 0; i < input2.length; i++) {
arr[input2[i]] = 1;
}//输入
let ans = 0;
let i = 0;
while (i <= N) {//枚举所有地址
let f = false;
for (let j = Math.min(i + R, N); j >= i - R + 1; j--) {//找对应的基站
if (arr[j] === 1) {
ans += M;
i = j + R - 1;//下一次我们需要枚举的地址为j+R
if (i + 1 === N) {//特例，因为我们不需要覆盖大于N的部分实数地址，所以只要覆盖到N即可
console.log(ans);
process.exit(0);
}
f = true;//一旦找到就记录，并且退出循环。
break;
}
}
if (!f) {//没找到输出-1
console.log(-1);
process.exit(0);
}
i++;
}
console.log(ans);
process.exit(0);
});
});
题目内容均收集自互联网，如如若此项内容侵犯了原著者的合法权益，可联系我: (CSDN网站注册用户名: 塔子哥学算法) 进行删除。
