Dropping tests POJ - 2976 

题意:  最大化

思路 : 设真实答案r* =   , 那么有 , 二分r,若,说明r太小.反之说明r太大.

这种形式的题可二分,证明可以看这篇博客 

#include<cstdio>
#include<vector>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e3+3;
const int MOD=1e9+7;
const double EPS=1e-12;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
ll n,k;
double a[N];
double b[N];
double t[N];
int sign(double x){
    return fabs(x) < EPS ? 0 : x>0 ? 1 : -1 ;
}
bool check(double mid){
    for(int i=1;i<=n;i++)
        t[i]=a[i]-b[i]*mid;
    sort(t+1,t+1+n);
    double sum=0.0;
    for(int i=k+1;i<=n;i++) sum+=t[i];
    if(sign(sum)>=0)    return true;
    else    return false;
}

int main(void){
    while(scanf("%lld%lld",&n,&k)==2){
        if(!n&&!k)  break;
        for(int i=1;i<=n;i++)   sf(a[i]);
        for(int i=1;i<=n;i++)   sf(b[i]);
        double l=0.0,r=1.0,res=0.0;
        for(int i=1;i<=20;i++){
            double mid=(l+r) / 2.0;
            if(check(mid))  res=mid,l=mid;
            else    r=mid;
        }
        printf("%lld\n",(ll)(0.5+100*res));
    }

    return 0;
}