/ ep / 题库 /

最大区间商

最大区间商

题目描述

给出两列整数a[i]和b[i],这两组整数的个数均为n
其中定义一个区间[L,R]的值为
\((\sum_{i=L}^{R}a[i])/(\sum_{i=L}^{R}b[i])\)
即a[i]中L到R的所有数的和/b[i]中L到R所有数的和
现在提问:在所有长度不小于m的区间中,最大的区间值是多少

输入

输入共三行
第一行:两个整数,分别为n和m,表示整数个数和最短区间长度
第二行,共n个整数,表示数列a[i]
第三行,共n个整数.表示数列b[i]

输出

共一行,一个实数,表示区间最大值
输出数据精确到两位小数

输入样例

5 2
10 7 1 3 8
9 10 6 6 3

输出样例

1.22

样例解释

最小区间长为2
区间[1,2]的值是0.78
区间[1,3]的值是0.72
区间[1,4]的值是0.68
区间[1,5]的值是0.97
区间[2,3]的值是0.50
区间[2,4]的值是0.50
区间[2,5]的值是0.76
区间[3,4]的值是0.33
区间[3,5]的值是0.80
区间[4,5]的值是1.22
所以,所有区间的最大值是1.22

数据范围

对于10%数据,m=1
对于30%数据,\(n\leq10\)
对于60%数据,\(n\leq1000\)
对于100%数据,\(1\leq n\leq100000,1\leq m<n,0<ai<10^8,0<bi<10^8\)

限制

每组数据1s,空间限制256M

信息

难度
3
分类
二分查找数学其他 点击显示
标签
(无)
递交数
7
已通过
1
通过率
14%
上传者

相关

在下列训练计划中:

新生入门训练计划