题目地址：POJ 2976 关于01分数规划的详细介绍都在这里了，传送门。 先写了发二分法的.时间是110ms. 二分代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-8;const int MAXN=40000+10;int n, m;double d[2000], a[2000], b[2000];bool check(double L){for(int i=0;i<n;i++){d[i]=a[i]-L*b[i];}sort(d,d+n);double tmp=0;for(int i=m;i<n;i++){tmp+=d[i];}return tmp>=0;}int main(){int i;while(scanf(“%d%d”,&n,&m)!=EOF&&n+m){for(i=0;i<n;i++){scanf(“%lf”,&a[i]);}for(i=0;i<n;i++){scanf(“%lf”,&b[i]);}double low=0.0, high=1.0, mid;while(high-low>eqs){mid=(low+high)/2;if(check(mid)){low=mid;}else high=mid;}printf(“%.0f\n”,low*100);}return 0;}
然后是迭代法，迭代法跟二分法的盲目二分的区别在于，，迭代法充分利用了R的值。时间大大减少，我的迭代法时间是47ms。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-8;const int MAXN=40000+10;int n, m;struct node{double a, b, d;}fei[2000];bool cmp(node f1, node f2){return f1.d<f2.d;}int main(){int i;while(scanf(“%d%d”,&n,&m)!=EOF&&n+m){for(i=0;i<n;i++){scanf(“%lf”,&fei[i].a);}for(i=0;i<n;i++){scanf(“%lf”,&fei[i].b);}double ans=0, tmp, p, q;while(1){tmp=ans;for(i=0;i<n;i++){fei[i].d=fei[i].a-tmp*fei[i].b;}sort(fei,fei+n,cmp);p=q=0;for(i=m;i<n;i++){p+=fei[i].a;q+=fei[i].b;}ans=p/q;if(fabs(ans-tmp)<=eqs) break;}printf(“%.0f\n”,ans*100);}return 0;}
人生谁无少年时，甜苦酸辛各自知。
