POJ 2976 Dropping tests

  • 2018-08-08
  • 5
  • 0


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 img. However, if you drop the third test, your cumulative average becomes img.


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.


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:



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个物品,每个物品有两个属性ab,删除k个物品,求剩下物品\frac{\sum a_{i}}{\sum b_{i}}的最大值(显然的错误算法——贪心)。

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

\therefore \sum a_{i}=x\times \sum b_{i}

\therefore \sum a_{i}-x\times \sum b_{i}=0

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