01分数规划入门题
附几个讲的比较好的博客（膜）
1.http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html
2.http://www.cnblogs.com/handsomecui/p/5116886.html?utm_source=tuicool&utm_medium=referral
3.http://blog.csdn.net/sdj222555/article/details/7491217
貌似目前只会用二分写
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;struct rec
{double a,b;
}c[1010];
double d[1010];
int n,k;bool fsgh(double R)
{double sum=0;for(int i=1;i<=n;i++) d[i]=c[i].a-R*c[i].b;sort(d+1,d+n+1);for(int i=n;i>(n-k);i--)sum+=d[i];return (sum>0)?true:false;
}double erfen(double l,double r)
{double mid;while(r-l>1e-6){mid=(l+r)/2;if(fsgh(mid)) l=mid;else r=mid;}return mid;
}int main()
{double mx;while(scanf("%d%d",&n,&k) && n){k=n-k;mx=0;for(int i=1;i<=n;i++) scanf("%lf",&c[i].a);for(int i=1;i<=n;i++) scanf("%lf",&c[i].b),mx=max(mx,c[i].a/c[i].b);printf("%.0f\n",erfen(0,mx)*100);}return 0;
}