xdu 1203 - put on make up 二分答案

  写了这么多题，总想不起来二分答案这种神方法。附带下sort的默认比较函数

sort 中的比较函 数

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
double a[10005],b[10005],t[10005];
int n,k;
bool ok(double mid)
{
    int i;
    double ans=0;
    for(i=0;i<n;i++)
        t[i]=a[i]-mid*b[i];
    sort(t,t+n,greater<double>());
    for(i=0;i<k;i++) ans+=t[i];
    return ans>0;
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        int i;
        double t;
        for(i=0;i<n;i++)
            scanf("%lf",&t),a[i]=log(t);
        for(i=0;i<n;i++)
            scanf("%lf",&t),b[i]=log(t);
        double l=1.0,r=3.0,mid;
        while(r-l>1e-8)
        {
            mid=(l+r)/2.0;
            if(ok(mid))l=mid;
            else r=mid;
        }
        printf("%.3f\n",l);
    }
}