首页 > 试题广场 >

gpa

[编程题]gpa

Kanade selected n courses in the university. The academic credit of the i-th course is s[i] and the score of the i-th course is c[i].

At the university where she attended, the final score of her is $\frac{\sum s[i]c[i]}{\sum s[i]}$

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

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 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

示例1

输入

3 1
1 2 3
3 2 1

2.33333333333

Delete the third course and the final score is

1≤ n≤ 10⁵

0≤ k < n

1≤ s[i],c[i] ≤ 10³

算法知识视频讲解

陌研

发表于 2021-10-05 20:43:40

【A.gpa题解】直接二分答案（答案为小数，注意精度）。对于当前答案D，如果有更大的结果，则∑(s[i]c[i])/∑s[i]>D\sum (s[i]c[i])/\sum s[i] > D∑(s[i]c[i])/∑s[i]>D，即∑(s[i]c[i])>∑(s[i]D)⇒ 展开全文

二分

难度：

0条回答 0收藏 6浏览

查看代码

gpa

扫一扫，把题目装进口袋