POJ2976 Dropping tests

题目链接：戳我
题目翻译的话。。。。去vjudge上看看，可以看到很好玩的翻译
其实是一个01规划的模板。
题目中会给我们两个数组a,b。
我们需要求的是选出n-k+1个数，使得他们的(frac{sum a[i]}{sum b[i]})最大
之后就可以转化一下为(sum a[i]-mid*b[i])
所以我们二分这个mid就行了。
具体详见代码；
代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 10010
#define eps 1e-6
using namespace std;
int n,k;
int a[MAXN],b[MAXN];
double c[MAXN];
int main()
{
	scanf("%d%d",&n,&k);
	while(n!=0||k!=0)
	{
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) scanf("%d",&b[i]);
		double l=0,r=100;
		while(l+eps<r)
		{
			double mid=(l+r)/2;
			for(int i=1;i<=n;i++) c[i]=a[i]-mid*b[i];
			sort(&c[1],&c[n+1]);
			double cur_ans=0;
			for(int i=n;i>k;i--) cur_ans+=c[i];
			if(cur_ans>=0) l=mid;
			else r=mid;
		}
		printf("%.0lf
",l*100);
		scanf("%d%d",&n,&k);
	}
	
	return 0;
}