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 ≤ ai ≤ bi ≤ 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个物品,每个物品有两个属性 a和 b,删除 k个物品,求剩下物品 ∑bi∑ai的最大值(显然的错误算法——贪心)。
设最后结果( n−k个物品 ∑bi∑ai的最大值)为 x,即 ∑bi∑ai=x
∴∑ai=x×∑bi
∴∑ai−x×∑bi=0
二分 x,在 n个物品中选出 (a−x×b)最大的 n−k个,求和得 ans,若 ans≥0则 ∑bi∑ai≥x,向右缩小二分区间,若 ans≤0则 ∑bi∑ai≤x,向左缩小二分区间,直到达到合适的精确度。
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;
}