http://poj.org/problem?id=2976
#include <cstdio>
#include<vector>
#include<iterator>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
ll a[1010];
ll b[1010];
double d[1010];
int n, k;
double eps=1e-6;
bool check(double L)
{
for(int i=1;i<=n;i++)
{
d[i]=1.0*a[i]-1.0*L*b[i];
}
sort(d+1,d+n+1,greater<double> () );
double sum=0;
for(int i=1;i<=n-k;i++)
{
sum+=d[i];
}
if(sum>=0) return true;
else return false;
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
if(n==0) break;
for(int i=1;i<=n;i++)
{
scanf("%lld",a+i);
}
for(int i=1;i<=n;i++)
{
scanf("%lld",b+i);
}
double Max=-1;
for(int i=1;i<=n;i++)
{
Max=Max>(1.0)*a[i]/b[i]?Max:(1.0)*a[i]/b[i];
}
double l=0,r=Max,mid,curr=0;
while(r-l>eps)
{
mid=(l+r)/2;
if(check(mid))
{
curr=mid;
l=mid;
// printf("%lf",curr);
}
else r=mid;
}
printf("%.0f\n",100*curr);
}
}
