题面描述

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

思路

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

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

因此，我们对于每一个地址$i$，我们都要进行$for~~ j = min(N, i+R)~~ to~~~ i-R+1，j-=1$的循环（这里枚举到$i-R+1$，而不枚举到$i-R$的原因在于一旦选择$i-R$这个基站，那么肯定存在大于$j$的部分实数地址无法被覆盖），从$min(N,i+R)$开始找基站，一旦找到就调用对应的基站。调用基站$j$后，那么我们范围$[j-R,j+R]$的所有地址都会被覆盖，因此，下一次我们需要枚举的地址应该从$j+R$开始（不是$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; // 将候选基站位置标记为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即可
                    cout << ans << endl; // 输出总费用
                    return 0;
                }
                f = true; // 标记找到基站
                break; // 跳出内层循环
            }
        }
        if (!f) { // 如果当前地址没有找到可用基站
            cout << -1 << endl; // 输出-1表示无法覆盖
            return 0;
        }
    }
    cout << ans << endl; // 输出最终所需的总费用
    return 0;
}

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

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 >= Math.max(i - R + 1, 0); j--) { // 确保 j 不小于 0
                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);
    });
});

题目描述

小明接到一个新课题，监测一整条河流的水质。

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

假设小明知道的河流是一条直线，请计算最少需要多少经费建设水质监测站才能完成对整条河流(也就是直线上的每一个实数点)的水质监测。

输入描述

输入第一行包含三个整数 $N$ , $R$ , $M$ .($1 \leq N \leq 3000$,$10 \leq R \leq 200,1 \leq M \leq 100000$ ) 输入第二行包含 $K$ 个整数 $a_1,a_2…a_K$ ,表示在高铁沿线的第$a_1，a_2…a_K$ 公里的地点可以建设基站.( $1 \leq K \leq N,0 \leq a_i \leq N$ )

输出描述

输出一个整数，表示最少花费的经费，如果所有候选地点均建设了基站还是无法覆盖则输出 "-1" 。

样例1

样例输入

100 20 114514
10 30 50

样例输出

-1

样例2

样例输入

80 50 114514
0 20 40 60

样例输出

114514