#P1565. 2023.05.17-暑期实习-第二题-河流水质监测
-
ID: 29
Tried: 84
Accepted: 17
Difficulty: 5
2023.05.17-暑期实习-第二题-河流水质监测
题目描述
小红接到一个新课题，监测一整条河流的水质。
目前小红选择了一条河流进行水质监测，长度为 N 公里。经过专业人员勘察，河流沿线有 K 个候选地点适合安装水质监测站，每个监测站可以覆盖的长度为半径 R 公里，单个监测站建设成本为 M 。
假设小红知道的河流是一条直线，请计算最少需要多少经费建设水质监测站才能完成对整条河流(也就是直线上的每一个实数点)的水质监测。
输入描述
输入第一行包含三个整数 N , R , M .(1≤N≤3000,10≤R≤200,1≤M≤100000 ) 输入第二行包含 K 个整数 a1,a2…aK ,表示在高铁沿线的第a1，a2…aK 公里的地点可以建设基站.( 1≤K≤N,0≤ai≤N )
输出描述
输出一个整数，表示最少花费的经费，如果所有候选地点均建设了基站还是无法覆盖则输出 "-1" 。
样例1
样例输入
100 20 114514
10 30 50
样例输出
-1
样例2
样例输入
80 50 114514
0 20 40 60
样例输出
114514
题面描述
塔子哥接到一项任务，需要在一条长为 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 >= 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);
});
});