04145: 放弃考试

binary search, http://cs101.openjudge.cn/practice/04145

在一门课程中，一共有n场考试。假如你在i场考试中可以答对bi道题中的ai道，那么你的累计平均分定义为：100·Σai/Σbi。已知你这i场考试的答题情况，并且允许你放弃其中的k场考试，请你确定你最高能够得到多少的累计平均分。

假设该课程一共有3门考试，你的答题情况为5/5，0/1和2/6。如果你每门都参加，你的累计平均分为100·(5+0+2)/(5+1+6)= 50分。如果你放弃第3场考试，你的累计平均分则提高到了100·(5+0)/(5+1)= 83.33 ≈ 83分。

输入

有多组测试数据，每组测试数据包括3行。每组测试数据第一行有两个数n和k，接下来一行有n个数ai，最后一行n个数bi。 (1 ≤ k < n ≤ 1000) (1 ≤ ai ≤ bi ≤ 1, 000, 000, 000)。输入的最后一行为0 0，不作处理。

输出

输出最高的累计平均分。（四舍五入到整数）

样例输入

样例输出

83
100

来源: http://poj.org/problem?id=2976

python

# 蒋子轩23工学院
def can_achieve(target,a,b,k):
    diffs=[a[i]-target*b[i] for i in range(len(a))]
    diffs.sort()
    #放弃k场考试后可以达到target
    return sum(diffs[k:])>=0
def max_avg_score(k,a,b):
    l,r=0,100
    while r-l>1e-5:
    	#非整数二分
        m=(l+r)/2
        if can_achieve(m,a,b,k):
            l=m
        else:
            r=m
    return m*100
while True:
    n,k=map(int,input().split())
    if n==0 and k==0:
        break
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(f'{max_avg_score(k,a,b):.0f}')

04145: 放弃考试 ​

04145: 放弃考试