P3853 [TJOI2007] 路标设置

题目描述

在一条公路上，有 $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++ 代码