OpenJudge

4145:放弃考试

总时间限制:
1000ms
内存限制:
65536kB
描述

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

假设该课程一共有3门考试,你的答题情况为5/50/12/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,不作处理。
输出
输出最高的累计平均分。(四舍五入到整数)
样例输入
3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0
样例输出
83
100
来源
http://poj.org/problem?id=2976
全局题号
12067
添加于
2016-10-26
提交次数
520
尝试人数
113
通过人数
36
您的评价 很水 简单 一般 较难 变态
  • 标签(多个标签用空格分隔):
  • 常用标签:
    递归   动态规划   贪心   搜索   枚举   模拟   数学   字符串处理   几何   高精度计算   图论  

共有25人评分

60.0%
16.0%
4.0%
4.0%
16.0%

已有的标签

贪心(7) 数学(7) 搜索(4) 动态规划(4) 枚举(4)