ACM最大比率问题：有N道题目,每道题目有不同的分值和难度,分别为Ai,Bi.要求从某一题开始连续选至少K道题目,满足分值和与难度和的比最大.例：N=7,K=3A4398992B2211211选择第3题到第6题

Question

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
这是上例最优解

Answer 1

O(n^2)直接枚举就好了,数据范围大的话可以分数规划做到O(nlgn),二分答案ans以后构造数列
C[] = A[] - B[] * ans ,然后O(n)时间做一次最大连续子段和即可