Dropping tests
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).
Source
题目大意：给定n组ai, bi的值（满足ai / bi <= 1）,
现在可以去除k组a, b， 使得100 * （∑ai / ∑bi）的值最大， 求其最大值
实际上， 这是一个裸的O1分数规划问题
下面， 我们了解一下01分数规划
所谓的01分数规划问题就是指这样的一类问题，给定两个数组，a[i]表示选取i的收益，b[i]表示选取i的代价。如果选取i，定义x[i]=1否则x[i]=0。每一个物品只有选或者不选两种方案，求一个选择方案使得R=∑(a[i]*x[i])/∑(b[i]*x[i])取得最值，即所有选择物品的总收益/总代价的值最大或是最小。 ——摘自Hhaile
本题即 在满足∑x[i] = n - k 的条件下， 求R的最大值
由 R=∑(a[i]*x[i])/∑(b[i]*x[i]) 有 ∑(a[i]*x[i]) - R∑(b[i]*x[i]) = 0
那么我们二分一个R,
若max(∑(a[i]*x[i]) - R∑(b[i]*x[i])) > 0, 则R还有更大值可取
反正， 若max(∑(a[i]*x[i]) - R∑(b[i]*x[i])) < 0， 就说明当前枚举的R过大
现在我们的主要任务就是求max(∑(a[i]*x[i]) - R∑(b[i]*x[i]))
∑(a[i]*x[i]) - R∑(b[i]*x[i]) = ∑(a[i]- R * b[i]) * x[i]
我们设d[i] = a[i]- R * b[i],
由于x[i]的值为0或1， 所以在没有限制的条件下，
d[i] > 0 的 x[i] 取1， d[i] < 0 的 x[i] 取0所得的∑(a[i]*x[i]) - R∑(b[i]*x[i]) 值最大
但对于本题， 我们有∑x[i] = n - k 的限制
显然， 我们取d[i]较大的(n - k)个数即可
综上， 我们二分R的值， 通过判断max(∑(a[i]*x[i]) - R∑(b[i]*x[i]))与0的关系判断R的合法性， 即可求出合法的R
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MaxN = 1010;
const double eps = 1e-8;
double Ans, F[MaxN];
int N, K;
double a[MaxN], b[MaxN];
inline bool check(const double &x) {
for (int i = 1; i <= N; ++i)
F[i] = a[i] - x * b[i];
sort(F + 1, F + N + 1);
double s = 0;
for (int i = K + 1; i <= N; ++i)
s += F[i];
return s >= -eps;
}
int main()
{
while (true) {
scanf("%d%d", &N, &K);
if (N == 0 && K == 0) break;
for (int i = 1; i <= N; ++i) scanf("%lf", &a[i]);
for (int i = 1; i <= N; ++i) scanf("%lf", &b[i]);
double L = 0, R = 1;
while (R - L > eps) {
double mid = (L + R) / 2;
if (check(mid)) {
Ans = mid;
L = mid;
}
else R = mid;
}
printf("%.0f\n", Ans * 100);
}
}
PS：在输出上有一个坑点， 我们用"%.lf"输出会出问题， 应该用"%.0f"输出来四舍五入答案值
评论 (0)
