最大累积平均成绩

题目描述

在某个课程中，你需要进行 $n$ 次测试。

成绩定义

如果你在共计 $b_i$ 道题的测试 $i$ 上的答对题目数量为 $a_i$，你的累积平均成绩就被定义为：

$$\frac{\sum_{i=1}^{n} a_i}{\sum_{i=1}^{n} b_i} \times 100$$

规则

给定您的考试成绩和一个正整数 $k$，如果您被允许放弃任何 $k$ 门考试成绩，您的累积平均成绩的可能最大值是多少。

示例

假设您进行了 $3$ 次测试，成绩分别为 $5/5, 0/1$ 和 $2/6$：

1. 不放弃任何成绩：

   • 总答对数：$5 + 0 + 2 = 7$
   • 总题数：$5 + 1 + 6 = 12$
   • 累积平均成绩：$\frac{7}{12} \times 100 \approx 58.33$

2. 放弃第三门成绩：

   • 总答对数：$5 + 0 = 5$
   • 总题数：$5 + 1 = 6$
   • 累积平均成绩：$\frac{5}{6} \times 100 \approx 83.33$

输入格式

输入包含多组测试用例，每个测试用例包含三行。

对于每组测试用例：

• 第一行包含两个整数 $n$ 和 $k$
• 第二行包含 $n$ 个整数，表示所有的 $a_i$
• 第三行包含 $n$ 个整数，表示所有的 $b_i$

当输入用例 $n=k=0$ 时，表示输入终止，且该用例无需处理。

输出格式

对于每个测试用例，输出一行结果，表示在放弃 $k$ 门成绩的情况下，可能的累积平均成绩最大值。

结果应四舍五入到最接近的整数。

数据范围

• $1 \le n \le 1000$
• $0 \le k < n$
• $0 \le a_i \le b_i \le 10^9$

输入样例

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

输出样例

83
100

样例解释

第一个测试用例：$n=3, k=1$

成绩数据：

• $a = [5, 0, 2]$
• $b = [5, 1, 6]$

情况分析：

1. 放弃第1门成绩：

   • 保留成绩：$(0/1), (2/6)$
   • 总答对数：$0 + 2 = 2$
   • 总题数：$1 + 6 = 7$
   • 平均成绩：$\frac{2}{7} \times 100 \approx 28.57$

2. 放弃第2门成绩：

   • 保留成绩：$(5/5), (2/6)$
   • 总答对数：$5 + 2 = 7$
   • 总题数：$5 + 6 = 11$
   • 平均成绩：$\frac{7}{11} \times 100 \approx 63.64$

3. 放弃第3门成绩：

   • 保留成绩：$(5/5), (0/1)$
   • 总答对数：$5 + 0 = 5$
   • 总题数：$5 + 1 = 6$
   • 平均成绩：$\frac{5}{6} \times 100 \approx 83.33$

最大值约为 $83.33$，四舍五入为 83

第二个测试用例：$n=4, k=2$

成绩数据：

• $a = [1, 2, 7, 9]$
• $b = [5, 6, 7, 9]$

寻找最优组合：

计算每门成绩的正确率：

1. $1/5 = 0.2$
2. $2/6 \approx 0.333$
3. $7/7 = 1.0$
4. $9/9 = 1.0$

最优策略：保留两个正确率最高的成绩（第3和第4门）

• 总答对数：$7 + 9 = 16$
• 总题数：$7 + 9 = 16$
• 平均成绩：$\frac{16}{16} \times 100 = 100$

输出：100

问题分析

数学形式

我们要最大化：

$$R = \frac{\sum_{i \in S} a_i}{\sum_{i \in S} b_i} \times 100$$

其中 $S$ 是选择的 $n-k$ 门成绩的集合。

等价问题

最大化 $R$ 等价于最大化比值 $\frac{\sum a_i}{\sum b_i}$。

0-1分数规划

这是一个典型的0-1分数规划问题：

对于给定的 $x$，检查是否存在集合 $S$（$|S| = n-k$）使得：

$$\frac{\sum_{i \in S} a_i}{\sum_{i \in S} b_i} \geq x$$

等价于：

$$\sum_{i \in S} (a_i - x \cdot b_i) \geq 0$$

算法步骤

1. 二分答案：二分查找 $x$（平均成绩/100）
2. 验证：对于给定的 $x$，计算 $c_i = a_i - x \cdot b_i$
3. 选择：选择 $n-k$ 个最大的 $c_i$
4. 判断：如果 $\sum c_i \geq 0$，则 $x$ 可行；否则不可行

精度处理

• 需要高精度二分（通常 $10^{-6}$ 或更高精度）
• 最终结果四舍五入到整数

时间复杂度

• 二分：$O(\log(\text{精度}))$
• 每次验证：$O(n \log n)$
• 总复杂度：$O(n \log n \log(\text{精度}))$

边界情况

• $k = 0$：不能放弃任何成绩
• $k = n-1$：只保留一门成绩，选择正确率最高的一门
• $a_i = 0$ 的情况
• $b_i$ 可能很大（$10^9$）

时空限制

• 时间限制：1秒
• 空间限制：64MB