主题

主题

 
   

Dropping tests

原题:http://poj.org/problem?id=2976

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 npositive 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).


题目大意:

(ctbb开始觉得题目有歧义,去看别人的博客,结果别人博客的翻译还糟糕一些……莫名WA)

给出n个二元组,删去其中k个,使得sigma(A[i])/sigma(B[i])最大。


个人解法:

01分数规划就好了。

还是记录一下自己的想法,怕以后忘了。

二分d,如果d是答案,那么满足对于任意的方案,d>=sigma(a)/sigma(b),即d*sigma(b)-sigma(a)>=0

如果存在d*sigma(b)-sigma(a)<0,说明d太小了还要调大。

如果任意d*sigma(b)-sigma(a)>0,说明d太大了不能被原式表示出来,要把d调小。

那么把所有的b取出来,然后做差,取最大的且为正数的k个扔去。


细节问题:

做这种题目总是有精度问题,况且还是在0.500000与0.499999的这样,然后第一位小数变为了四舍五入的判断符,于是就很纠结。

如果无脑,把标识符一位的数字加上标识符一位的单位小数。比方说上例,把两个数字都加上0.1。那么对于这一种情况可以变为0.600000与0.599999,可以解决。

但是这样无脑让0.433333变成了0.533333,本应该保留到0.4,就保留到了0.5。

一种方法是把其规定的输出位*10,然后保留之后再/10。

但是这样又会让0.88475这样的小数变为0.885,之后变为0.89。

此题告诉我们,最好的办法就是什么也不想。eps变为题目要求的精度的1/100以下即可。

(亲测有效……)


代码如下:

https://code.csdn.net/snippets/2306331

 
 
评论