牛客网暑期ACM多校训练营(第五场)A gpa

  • 2018-08-08
  • 14
  • 0

Description:

At the university where she attended, the final score of her is img

Now she can delete at most k courses and she want to know what the highest final score that can get.

Input:

The first line has two positive integers n,k

The second line has n positive integers s[i]

The third line has n positive integers c[i]

Output:

Output the highest final score, your answer is correct if and only if the absolute error with the standard answer is no more than 10^{-5}

Sample Input:

3 1
1 2 3
3 2 1

Sample Output:

2.33333333333

Hint:

Delete the third course and the final score is \frac{2\times 2+3\times 1}{2+1}=\frac{7}{3}

题目链接

n门课,每门课有两个属性sc,删除k门课,使\frac{\sum s[i]\times c[i]}{\sum s[i]}最大。

01分数规划,设最终结果max(\frac{\sum s[i]\times c[i]}{\sum s[i]})=x,则\sum s[i]\times c[i]-x\times\sum s[i]=0,所以选择(s\times c-x\times s)最大的n-k门课,不断二分x直到找到最大值并达到合适的精度。

AC代码:

评论

还没有任何评论,你来说两句吧