TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4250
  • 题目
  • P4250小区划分
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    问题描述

    一条街道的两侧各连续坐落着 N 座单元楼。现在要为这些单元楼划分居民校区。

    规则如下:

    1. 每个小区只能由同一侧连续的若干座单元楼组成。且两侧都恰有 K 个小区(每个小区至少有一栋楼)。

    2. 两侧的小区划分规则应该相同,比如,若左边的房子被分成 {1,2},{3} 这两个小区,那么右边也应该如此。

    这样两边合计一共有 K 对小区。

    用 ai,bii​​,b​i​​ 表示左右两边每座楼的人口在同侧所有单元楼总人口中所占的百分比,定义一个小区的相对拥挤程度为其人口百分比之和(左边就是对应 aia_ia​i​​ 的和,右边是对应 bib_ib​i​​ 的和)。定义这条街道的总拥挤程度为左右两边 KKK 对小区的相对拥挤程度之差的绝对值之和。

    现在,请你求出可能的最大拥挤程度。

    输入格式

    第一行两个整数 N 和 k。

    第二行 N 个实数,第 i 个数为 ai​i​​。

    第三行 N 个实数,第 i 个数位 bi​i​​。

    输出格式

    一个实数,表示这条街道的最大相对拥挤程度,保留到小数点后六位。

    样例输入

    3 2
    0.1 0.75 0.15
    0.4 0.3 0.3

    样例输出

    0.600000

    提示

    样例解释

    1号楼一个小区,(2,3) 号楼 1个小区。

    这样相对拥挤程度最大为 abs(0.1−0.4)+abs(0.75+0.15−(0.3+0.3))=0.6。

    对于 30%的数据:n≤20。

    对于 100% 的数据:n≤800,k≤80。

    保证 ∑ai=1,∑bi=111i​​=1,∑b​i​​=1。


    来源  1s