早教吧作业答案频道 -->数学-->
ACM最大比率问题：有N道题目,每道题目有不同的分值和难度,分别为Ai,Bi.要求从某一题开始连续选至少K道题目,满足分值和与难度和的比最大.例：N=7,K=3A4398992B2211211选择第3题到第6题
题目详情
ACM最大比率问题：有N道题目,每道题目有不同的分值和难度,分别为Ai,Bi.
要求从某一题开始连续选至少K道题目,满足分值和与难度和的比最大.
例：N=7,K=3
A 4 3 9 8 9 9 2
B 2 2 1 1 2 1 1
选择第3题到第6题,比为（9+8+9+9)/（1+1+2+1）=7
这是上例最优解
要求从某一题开始连续选至少K道题目,满足分值和与难度和的比最大.
例：N=7,K=3
A 4 3 9 8 9 9 2
B 2 2 1 1 2 1 1
选择第3题到第6题,比为（9+8+9+9)/（1+1+2+1）=7
这是上例最优解
▼优质解答
答案和解析
O(n^2)直接枚举就好了,数据范围大的话可以分数规划做到O(nlgn),二分答案ans以后构造数列
C[] = A[] - B[] * ans ,然后O(n)时间做一次最大连续子段和即可
C[] = A[] - B[] * ans ,然后O(n)时间做一次最大连续子段和即可
看了 ACM最大比率问题：有N道题...的网友还看了以下：
初一数学问题1.若a、b、c是△ABC三边长,试化简|a-b-c|+|b-c-a|+|c-a-b| 2020-05-17 …
一道二项式的题1设A=3^7+C(2,7)·3^5+C(4,7)·3^3+C(6,7)·3,B=C 2020-05-21 …
计算应用题小明在计算1/A（即A分之1）×（1/B+1/C)(A、B、C都是不相等的整数）时,算成 2020-06-14 …
求数学高手解答一道令我十分纠结的题已知a,b,c都大于0小于1.求证：(1-a)b,(1-b)c, 2020-06-17 …
关于杜甫的问题1、下列对杜甫极尽道德人格推崇的是哪位?(单选题)1分A:颜真卿B:范仲淹C:朱熹D 2020-07-26 …
化简的题1.B∠A∠0∠1∠C("∠"为小于符号)|A|=|B|化简|A|÷A+|B|÷B+|C| 2020-08-01 …
i几道关于高中的数学题1.若A={a,0,1},B={c+b,1/b+a,1},且A=B,则a=, 2020-08-01 …
望高手赐教,高一数列……递推公式a(n+1)=[a(n)+a]/[a(n)+b]a,b皆为非零常数 2020-08-01 …
比例算术题?1、A产品含量95%,B产品含量50%,A与B是4:1配成C产品,C产品的含量是多少?2 2020-11-28 …
POJ试题：TimeLimit:1000MSMemoryLimit:10000K我们的问题是：对于每 2020-12-01 …