| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 11367 | Accepted: 3962 |
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
题目链接：POJ 2976
题意：给你N个物品，每一个物品有它的属性ai与bi，求丢掉K个物品后使留下来的N-K个物品的${\Sigma a_i} \over {\Sigma b_i}$最大化。
如果没听过01分数规划可以先看这篇文章：传送门1，传送门2，然后我想说的是其中对$r={{\Sigma a_i*x_i} \over {\Sigma b_i*x_i}}$的移项变形可以得到：$0={\Sigma a_i*x_i}-r*{\Sigma b_i*x_i}$
然后就是这里搞了一会儿才弄明白（数学渣没办法），想一想是不是很想熟悉的二次函数$y=ax^2+bx+c$的形式，有时候我们也利用$0=ax^2+bx+c$来推导二次函数，可以发现后者是前者的特殊情况，当y=0时前者便成了后者，或者说后者求出来的解是在自变量轴上的交点。那么上面那个函数同理，若把0改成F(r)，则可以发现这是一个图像，由于bixi大于等于0，因此至少是关于r递减，又由于这个变量又受x_i集合的取值影响，这个图像实际上就像我们要使得$0={\Sigma a_i*x_i}-r*{\Sigma b_i*x_i}$成立，显然需要当$r=r_i$的时候$F(r)=0$，但是这样的取值$r_i$可以有很多个，那么我们要找到最靠右的那个点作为答案即可。当然这题还用到了贪心的思想，因为取哪个是随意的，当然取每一次取最优的
代码：
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <numeric>
#include <cstring>
#include <bitset>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1010;
const double eps = 1e-5;
double a[N], b[N], d[N]; int main(void)
{
int n, k, i;
while (~scanf("%d%d", &n, &k) && (n | k))
{
for (i = 0; i < n; ++i)
scanf("%lf", a + i);
for (i = 0; i < n; ++i)
scanf("%lf", b + i);
double L = 0, R = 1e9 + 7, ans = 0;
int res = n - k;
while (fabs(R - L) >= eps)
{
double mid = (L + R) / 2.0;
for (i = 0; i < n; ++i)
d[i] = a[i] - mid * b[i];
sort(d, d + n, greater<double>());
double temp = 0;
for (i = 0; i < res; ++i)
temp += d[i];
if (temp > 0)
{
L = mid;
ans = mid;
}
else
R = mid;
}
printf("%.0f\n", 100.0 * ans);
}
return 0;
}