Description:

In a certain course, you take n tests. If you get ai out of bi questions correct on test i, your cumulative average is defined to be

.

Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.

Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .

Input:

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤k < n. The second line contains n integers indicating ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ aibi ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

Output:

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

Sample Input:

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

Sample Output:

83
100

Hint:

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

题目链接

01分数规划题目。给出 n n n个物品,每个物品有两个属性 a a a b b b,删除 k k k个物品,求剩下物品 a i b i \frac{\sum a_{i}}{\sum b_{i}} biai的最大值(显然的错误算法——贪心)。

设最后结果( n k n-k nk个物品 a i b i \frac{\sum a_{i}}{\sum b_{i}} biai的最大值)为 x x x,即 a i b i = x \frac{\sum a_{i}}{\sum b_{i}}=x biai=x

a i = x × b i \therefore \sum a_{i}=x\times \sum b_{i} ai=x×bi

a i x × b i = 0 \therefore \sum a_{i}-x\times \sum b_{i}=0 aix×bi=0

二分 x x x,在 n n n个物品中选出 ( a x × b ) (a-x\times b) (ax×b)最大的 n k n-k nk个,求和得 a n s ans ans,若 a n s 0 ans\ge0 ans0 a i b i x \frac{\sum a_{i}}{\sum b_{i}}\ge x biaix,向右缩小二分区间,若 a n s 0 ans\le0 ans0 a i b i x \frac{\sum a_{i}}{\sum b_{i}}\le x biaix,向左缩小二分区间,直到达到合适的精确度。

AC代码:

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout << #x << "=" << x << endl;
#define ArrayDebug(x,i) cout << #x << "[" << i << "]=" << x[i] << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e7 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-6;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
	char c;
	int sgn;
	if (c = getchar(), c == EOF) {
		return 0;
	}
	while (c != '-' && (c < '0' || c > '9')) {
		c = getchar();
	}
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0' && c <= '9') {
		ret = ret * 10 + (c - '0');
	}
	ret *= sgn;
	return 1;
}
template <class T>
inline void out(T x) {
	if (x > 9) {
		out(x / 10);
	}
	putchar(x % 10 + '0');
}

int n, k;
vector<int> a, b;

bool check(double x) {
	vector<double> temp(n, 0.0);
	for (int i = 0; i < n; ++i) {
		temp[i] = a[i] - x * b[i];
	}
	sort(temp.begin(), temp.end());
	double ans = 0;
	for (int i = n - 1; i >= k; --i) {
		ans += temp[i];
	}
	return ans >= 0;
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	while (read(n) && read(k) && n + k) {
		a.assign(n, 0);
		b.assign(n, 0);
		for (int i = 0; i < n; ++i) {
			read(a[i]);
		}
		for (int i = 0; i < n; ++i) {
			read(b[i]);
		}
		double left = 0, right = 1;
		while (right - left > eps) {
			double mid = (left + right) / 2;
			if (check(mid)) {
				left = mid;
			}
			else {
				right = mid;
			}
		}
		printf("%.0f\n", left * 100);	//G++
		// printf("%.0lf\n", left * 100); C++
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}