ACM最大比率问题：有N道题目，每道题目有不同的分值和难度，分别为Ai,Bi。 20
要求从某一题开始连续选至少K道题目，满足分值和与难度和的比最大。例：N=7，K=3A4398992B2211211选择第3题到第6题，比为（9+8+9+9)/（1+1+2...
要求从某一题开始连续选至少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
这是上例最优解 展开
例：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
这是上例最优解 展开
3个回答
展开全部
O(n^2)直接枚举就好了,数据范围大的话可以分数规划做到O(nlgn),二分答案ans以后构造数列
C[] = A[] - B[] * ans ,然后O(n)时间做一次最大连续子段和即可
C[] = A[] - B[] * ans ,然后O(n)时间做一次最大连续子段和即可
本回答由网友推荐
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
