P3853 [TJOI2007] 路标设置
时间: 2023-09-17 10:08:58 浏览: 188
题目描述
在一条公路上,有 $n$ 个路标,第 $i$ 个路标的位置为 $x_i$,每个路标上都有一个数字 $a_i$。现在需要在这条公路上设置 $m$ 个路障,每个路障的位置为 $y_i$,每个路障会覆盖一段长度为 $l_i$ 的区间 $[y_i-l_i,y_i+l_i]$,其中 $l_i$ 是正整数。
对于每个路障,它会覆盖的区间内的路标的数字 $a_i$ 的和为 $s_i$,即 $s_i=\sum_{j=1}^n[a_j\in[y_i-l_i,y_i+l_i]]a_j$。
现在需要在不超过 $k$ 个路障的前提下,最大化所有路障覆盖的数字和的最小值。
输入格式
第一行包含三个整数 $n,m,k$。
接下来 $n$ 行,每行包含两个整数 $x_i,a_i$。
接下来 $m$ 行,每行包含两个整数 $y_i,l_i$。
输出格式
输出一个实数,表示最大化所有路障覆盖的数字和的最小值,保留 $2$ 位小数。
数据范围
$1\leq n,m\leq 200$,
$1\leq k\leq 10$,
$\leq x_i,y_i\leq 10^9$,
$1\leq a_i,l_i\leq 10^6$
输入样例1
5 2 1
1 2
2 3
3 4
4 5
5 6
3 1
7 1
输出样例1
3.50
输入样例2
5 2 2
1 2
2 3
3 4
4 5
5 6
3 1
7 1
输出样例2
2.50
算法1
(二分答案+贪心) $O(m^2\log w)$
二分答案+贪心
时间复杂度
参考文献
python3 代码
C++ 代码
算法2
(暴力枚举) $O(n^2m^2)$
blablabla
时间复杂度
参考文献
C++ 代码
阅读全文