牛客多校，gpa

链接：https://www.nowcoder.com/acm/contest/143/A
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

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

输入

复制

3 1
1 2 3
3 2 1

输出

复制

2.33333333333

说明

Delete the third course and the final score is 

备注:

1≤ n≤ 105

0≤ k < n

1≤ s[i],c[i] ≤ 103

题意：

给 n 门课的学分和成绩，求最大加权平均值，其中最多可以删去 k门课程。

思路：

二分枚举答案。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
double mid;
struct node{
    int s,c;
    bool operator<(const node&p)const {
        return s*(c-mid)>p.s*(p.c-mid);
    }
}a[maxn];
 
int n,k;
bool check(){
    double l=0,r=0;
    sort(a+1,a+1+n);
    for (int i=1; i<=n-k; i++){
        l+=a[i].s*a[i].c;
        r+=a[i].s;
    }
    return l/r>=mid;
}
int main(){
    scanf("%d%d",&n,&k);
    for (int i=1; i<=n; i++) scanf("%d",&a[i].s);
    for (int i=1; i<=n; i++) scanf("%d",&a[i].c);
    double l=0,r=(double)(1e7);
    while(r-l>1e-12){
        mid=(l+r)/2;
        if(check()) l=mid;
        else r=mid;
    }
    printf("%.7f\n",l);
    return 0;
}