A2199. Wifi 设置
编程题
普及/提高-
知识点
题目描述
给出在同一条直线上的n个点和两个数A，B，现在要在这条直线上放置若干个信号塔，每个信号塔有一个r值，假设它的位置是x，则它能覆盖的范围是x-r~x+r，放置一个信号塔的花费是A+B*r，问要覆盖所有的点最小的花费是多少。
输入格式
* 第 1 行：三个空格分隔的整数：N A B （0 <= A， B <= 1000）。
* 第 2..1+N 行：每行包含一个整数
0..1,000,000 描述了 FJ 的一头奶牛的位置。
* 第 2..1+N 行：每行包含一个整数
0..1,000,000 描述了 FJ 的一头奶牛的位置。
输出格式
* 第 1 行：为所有奶牛提供无线覆盖的最低成本。
输入输出样例
输入 #1
3 20 5 7 0 100
输出 #1
57.5
说明/提示
在位置 7、0 和 100 有 3 头奶牛。安装功率r的基站成本为20 + 5 * r。
最佳解决方案是在位置 3.5（功率为 3.5）和位置 100（功率为 0）构建另一个基站。第一个基站覆盖奶牛 1 和 2，第二个基站覆盖奶牛 3。
最佳解决方案是在位置 3.5（功率为 3.5）和位置 100（功率为 0）构建另一个基站。第一个基站覆盖奶牛 1 和 2，第二个基站覆盖奶牛 3。