M22528:厚道的调分方法

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

看到大家在数算课学的很努力，谢老师决定想把大家最终的成绩调高一点。谢老师打算把每人的分数由x分调整为ax+1.1^ax分，其中 a 是一个 0 到 1 之间的常数。

为了简单起见，我们假设调整后分数超过100分也没有问题。

为了方便输出格式，我们假设 a = b / 1000000000，其中 b 是不超过1000000000的正整数。

给定全班同学的原始成绩，请帮谢老师求出一个最小的正整数 b ，使得调分之后优秀（85分及以上）的人数比例不小于 60% 。

（本题为假想情形，调分方法与现实无关）

输入

一行以空格分隔的浮点数，分别代表每个学生的原始成绩。学生数量不超过100000，每个学生的原始成绩是一个在 [40, 100] 区间的浮点数。

输出

一个整数，使得至少60%学生不小于85分的正整数b的最小值。

样例输入

50.5 100.0 40.0

样例输出

791111236

提示

调分所用函数比较复杂，我们难以得到它的逆的解析解，但可以看出它是单调的
程序的运行时间可能受到两个方面的影响：b的范围大、学生数量多
使用整数b除以10^9的值来代替浮点数a做运算，主要是为了避免浮点数误差和四舍五入导致可能openjudge评判答案不对的问题（因为openjudge要求答案完全一致才算对），可能略微提高了题目难度。现实生活中可以全程用浮点数a进行运算
语法提示：

float(x)可以把字符串x转为浮点数，int(x)可以把浮点数x向下取整转为整数输入可用[float(x) for x in input().split()]来得到成绩的数组 a的b次方在python的写法是 a ** b

【李佳聪 24工学院】二分查找，只需找到60%节点处的学生成绩并与85分比较即可。

python

grade = [float(x) for x in input().split()]
le = len(grade)
grade.sort()
targ = grade[int(le * 0.4)]
left = 0
right = 1000000000 + 1
ans = 0
while left < right:
    mid = (left + right) // 2
    gd = targ * mid / 1000000000 + 1.1 ** (targ * mid / 1000000000)
    if gd >= 85:
        ans = mid
        right = mid
    else:
        left = mid + 1
print(left)

总结题目要求：

给定原始成绩数组。
调整公式：new_score = a * x + 1.1 ** (a * x)
a = b / 1e9
找最小的正整数 b，使得调整后成绩 ≥ 85 分的学生比例 ≥ 60%。

思路：

new_score 随 b 增大是单调增加的（因为 a 增大，a*x和1.1^(a*x)都会增大）。
所以可以二分答案b：从1到10^9之间找最小的满足条件的b。
每次给定一个b，计算每个学生的调后分数，看够不够 60% 达到85。

代码直接上：

python

def is_ok(b, scores):
    a = b / 1e9
    cnt = 0
    threshold = 0.6 * len(scores)
    for x in scores:
        new_score = a * x + 1.1 ** (a * x)
        if new_score >= 85:
            cnt += 1
    return cnt >= threshold


def main():
    scores = [float(x) for x in input().split()]

    l, r = 1, 10 ** 9 + 1
    ans = -1
    while l < r:
        mid = (l + r) // 2
        if is_ok(mid, scores):
            ans = mid
            r = mid
        else:
            l = mid + 1

    print(ans)


if __name__ == "__main__":
    main()

解释一下：

is_ok(b, scores)：判断当前这个b，调整后有没有60%人达到85分。
二分法不断缩小范围，找到最小的符合要求的b。

补充小知识（很重要！）：

(n * 6 + 9) // 10 是为了模拟向上取整的60%。
- 比如 n=5，(5*6+9)//10 = 3，要求3个人及以上。
- 比如 n=100000，需要60000人及以上。
避免直接用浮点数比较比例，因为浮点数有误差。

python

import math

def is_ok(b, scores, needed, log_1p1):
    a = b / 1e9
    count = 0
    for x in scores:
        ax = a * x
        new_score = ax + math.exp(ax * log_1p1)
        if new_score >= 85:
            count += 1
            if count >= needed:
                return True
    return False

def main():
    scores = [float(x) for x in input().split()]
    n = len(scores)
    needed = (n * 6 + 9) // 10  # 向上取整，不小于60%

    log_1p1 = math.log(1.1)  # 只算一次，1.1的自然对数

    l, r = 1, 10**9
    ans = -1
    while l <= r:
        mid = (l + r) // 2
        if is_ok(mid, scores, needed, log_1p1):
            ans = mid
            r = mid - 1
        else:
            l = mid + 1

    print(ans)

if __name__ == "__main__":
    main()

M22528:厚道的调分方法 ​

M22528:厚道的调分方法