A07 01分数规划

/*
题意：有n对数（ai,bi）
求从n中选k对，∑ai/∑bi最大。

思路：01分数规划。
我们有一种方法可以验证存在k对数满足 ∑ai/∑bi≥L，即bool check(L) 
通过不断的加大L试探check(L)是否为True，最后得到最大的L
 
具体方法和原理： 
∑ai/∑bi≥L  转换一下：∑ai-L*∑bi≥0
即：a1 + a2 ……+ a(n-k)  -  L*b1 -L*b2……-L*b(n-k)  ≥0
即：(a1 - L*b1) + (a2 - L*b2) + (a(n-k) - L*b(n-k)) ≥0  （1式） 
当L确定时，每一对数的贡献值是确定的为： (ai - L*bi)
要使得 （1式） 满足，每一对数的贡献值排序，取最大的k 对 
用二分枚举L。
单调性证明：当L增加时每一对的贡献值(ai - L*bi)都减少，故虽然最大k对有变动，
但 最大k对贡献值和在减少。 

*/

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const double eps=1e-6;
int n,k;
double a[N],b[N],c[N];
bool check(double L)
{
    for(int i=1;i<=n;i++) c[i]=a[i]-L*b[i];
    sort(c+1,c+1+n);
    double ans=0;
    for(int i=n;i>=n-k+1;i--) ans+=c[i];
    return ans>=0;
}
int main()
{
    scanf("%d%d", &n, &k); 
    for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
    for(int i=1;i<=n;i++) scanf("%lf",&b[i]);
    double l=0, r=1,mid;
    while(fabs(r-l)>eps)
    {
        mid =(l+r)/2;
        if(check(mid)) l=mid;
        else           r=mid;
    }
    printf("%lf\n", l  ) ;
    return 0;
}