2154.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2154 on 2006-01-28 at 00:07:06 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 1024;
const double eps = 1e-2;

int main()
{
	int n, k, i;
	double num[MAX], den[MAX], r[MAX];

	while(scanf("%d %d", &n, &k) != EOF && n != 0) {
		for(i = 0; i < n; i++) scanf("%lf", &num[i]), num[i] *= 100;
		for(i = 0; i < n; i++) scanf("%lf", &den[i]);
		double l = 0, h = 100;
		while(h - l > eps) {
			double mid = (l + h) / 2;
			for(i = 0; i < n; i++) r[i] = num[i]-den[i]*mid;
			sort(r, r+n); double sum = 0;
			for(i = k; i < n; i++) sum += r[i];
			if(sum > -eps) l = mid;
			else h = mid;
		}
		printf("%.0lf\n", (h+l)/2);
	}
	
	return 0;
}