本文共 1889 字，大约阅读时间需要 6 分钟。
为了解决这个问题，我们需要找到一种方法来确定在允许删除 k 个测试成绩的情况下，剩下的 n-k 个测试的平均分的最大值。我们可以使用二分查找来确定这个最大平均值。
问题分析：我们需要找到一个子集，使得删除 k 个测试成绩后，剩下的测试成绩的平均分最大化。平均分的计算公式为总分除以总题数，因此我们需要在总分和总题数之间找到一个平衡点。
二分查找：我们使用二分查找来确定最大的平均值。对于每个中间值 mid，我们需要检查是否存在一个子集，使得这个子集的总分之和至少为 mid 倍的总题数。
贪心策略：对于每个中间值 mid，我们计算每个测试成绩对该中间值的贡献值，并选择贡献值最大的 n-k 个测试成绩。这样可以确保我们对每个中间值进行最优的检查。
转换问题：我们将每个测试成绩转换为贡献值 s_i = a_i - mid * b_i，这样我们就可以通过选择最大的 n-k 个贡献值来确定是否存在满足条件的子集。
import sysdef main(): input = sys.stdin.read().split() ptr = 0 while True: n = int(input[ptr]) k = int(input[ptr+1]) ptr += 2 a = list(map(int, input[ptr:ptr+n])) ptr += n b = list(map(int, input[ptr:ptr+n])) ptr += n if n == 0 and k == 0: break if k == 0: total = sum(a) total_b = sum(b) avg = total / total_b print(round(avg)) continue S = sum(a) T = sum(b) low = 0.0 high = 100.0 best = 0.0 epsilon = 1e-9 while high - low > epsilon: mid = (low + high) / 2 s = [] for i in range(n): si = a[i] - mid * b[i] s.append(si) s.sort() sum_s = 0.0 for i in range(n - k): sum_s += s[i] if sum_s >= 0: best = mid low = mid + epsilon else: high = mid - epsilon avg = best print(round(avg + epsilon / 2))if __name__ == "__main__": main()
这种方法确保了我们能够高效地找到最优解，时间复杂度主要由二分查找和排序决定，为 O(n log n)，适用于给定的输入规模。
转载地址：http://shjj.baihongyu.com/