poj 2976 Dropping tests (最大化平均值：二分查找)

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#define inf 0x3f3f3f3f
using namespace std;
const int max_n=1050;
int n,k;
int w[max_n];
int v[max_n];
double y[max_n];
bool c(double x)
{
    for(int i=0;i<n;i++)
        y[i]=v[i]-x*w[i];
    sort(y,y+n);

    double sum=0;
    for(int i=0;i<k;i++)
    {
        sum+=y[n-i-1];
    }
    return sum>=0;
}
void solve()
{
    double lb=0,ub=inf;
    for(int i=0;i<100;i++)
    {
        double mid=(lb+ub)/2;
        if(c(mid))lb=mid;
        else ub=mid;
    }
    int ans=(int)round(ub*100);
    printf("%d ",ans);
}
int main()
{
#ifndef ONLINE_JUDGE
   freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
    while(scanf("%d%d",&n,&k)==2)
    {
        if(!n&&!k)break;
        for(int i=0;i<n;i++)scanf("%d",&v[i]);
        for(int i=0;i<n;i++)scanf("%d",&w[i]);
        k=n-k;
        solve();
    }
    return 0;
}