POJ 2976 (01分数规划)

题目链接：http://poj.org/problem?id=2976

01分数规划是这样的一类问题，有一堆物品，每一个物品有一个收益ai，一个代价bi，我们要求一个方案使选择的∑ai/∑bi最大。

二分(x),把 (a[i] - b[i] * x) 排序，取前 (n-k) 大判断即可

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 1010;
const double eps = 1e-6;

int n,k; 
int a[maxn],b[maxn];
double p[maxn];

bool check(double t){
	for(int i=1;i<=n;++i) p[i] = 1.0 * a[i] - 1.0 * b[i] * t;
	sort(p+1,p+1+n);
	double res = 0;
	for(int i=n;i>=k+1;--i){ res += p[i]; }
	return res >= 0;
}

void binary(){
	double l = 0, r = 1.0;
	while(r-l > eps){
		double mid = (l+r) / 2;
		if(check(mid)){
			l = mid;
		}else{
			r = mid;
		}
	}
 	printf("%.0lf
",l*100);
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	while(1){
		n = read(), k = read();
		if(n==0 && k==0) break;
		
		for(int i=1;i<=n;++i) a[i] = read();
		for(int i=1;i<=n;++i) b[i] = read();
		
		binary();
	}
	
	return 0;
}