题目描述

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

∑𝑠[𝑖]𝑐[𝑖] / ∑𝑠[𝑖].

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≤ n≤ 1e5,
0≤ k < n,
1≤ s[i],c[i] ≤ 1e3

样例

输入
3 1
1 2 3
3 2 1
输出
2.33333333333
说明
Delete the third course and the final score is 
2 ∗ 2 + 3 ∗ 1 / (2 + 1) = 7 / 3​

(二分) $O(N * log2(N))$

其他部分套模板就行，这里主要说一下check函数。对于每次查找结果有

∑s[i]c[i] / ∑s[i] < mid （这里以小于为例）,但是这样做存在问题，就是不太好确定删除的课程
那么我们可以考虑变化一下形式，将上式变形得到

∑s[i]c[i] < ∑s[i]mid, 移项得到,

∑s[i]c[i] - ∑s[i]mid < 0, 即

∑s[i] (c[i] - mid) < 0;

每次计算上式去除前k个小（因为可以删除k门课程）的结果即可

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
double s[N], c[N], val[N];
int n, k;
bool check(double x)
{
    double sum = 0;
    for (int i = 0; i < n; i++)
        val[i] =  s[i] * (c[i] - x);
    sort(val, val + n);
    for (int i = k; i < n; i++)
        sum += val[i];
    return sum < 0;
}
void solve()
{
    for (int i = 0; i < n; i++)
        cin >> s[i];
    for (int i = 0; i < n; i++)
        cin >> c[i];
    double l = 0, r = 1e3;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    printf("%f", l);
}
int main()
{
    cin >> n >> k;
    solve();
    return 0;
}