22491: 冲刺GPA的贪心之路

greedy, http://cs101.openjudge.cn/practice/22491/

Hellen是大一的学生，这学期她选修了若干门课程，快期末考试了，她准备好好地利用周末复习一下功课，争取学分绩点得到最大的提高。但她这学期选的课有点多，只能利用周末复习，有时候周末还有一些事情，不是每个周末都能投入同样时间。假设某周末她可以每天复习h小时，星期六加星期日两天一共可以投入复习的时间是2*h小时。为了保证所有的课程都复习到，她预计每门课程需要投入基础复习时间0.5小时。剩余的时间如何分配呢？

假设她一共有m门课程要考试，她发现自己对不同的课程有不同的擅长程度，比如课程A，在基础复习时间之后，每多复习1小时，估计会使成绩提升2.5分（只是时间收益比，非要按整数小时分配时间）；比如课程B，每多复习1小时，估计会使成绩提升1.5分。此外，为了尽量使各科都有提高，每门课程成绩提高总分预计为5分时，不再分配时间。

Hellen该如何分配自己的周末时间，使得复习效果达到她的最高预期？请问在这个策略和状态下，hellen最多能提高多少学分积（学分积=每门课提高的分数×学分之和）？备注：每门课的基础复习时间0.5小时不对提高学分积产生贡献

输入

输入的第一行为某周末一天可以投入的总复习时间h小时，正整数h（6<=h<=10); 第二行为课程门数，正整数m(1<=m<=10); 其余m行，每行对应一门课程，由实数s和c组成，分别为多复习一门课程一小时预计提高的分数s和该课程的学分c，中间用空格隔开。

输出

Hellen最多能提高多少学分积？输出为1行，保留1位小数。

样例输入

10
4
1.000000 1.000000
2.000000 1.000000
2.500000 1.000000
1.000000 1.000000

样例输出

20.0

python

def max_gpa_increase(h, courses):
    # 总复习时间，扣除每门课的基础复习时间
    total_time = 2 * h - 0.5 * len(courses)

    # 计算每门课程的性价比：每增加一小时复习时间所能提高的分数乘以学分
    for course in courses:
        course.append(course[0] * course[1])  # 将性价比添加到每个课程的信息中

    # 按性价比从高到低排序课程
    courses.sort(key=lambda x: -x[2])

    total_increase = 0  # 初始化总分提高
    for course in courses:
        if total_time <= 0:
            break
        # 计算当前课程最多可以分配的复习时间
        max_time_for_course = min(5 / course[0], total_time)
        total_time -= max_time_for_course
        # 计算当前课程的分数提高并累加到总分提高
        total_increase += max_time_for_course * course[0] * course[1]

    return total_increase


# 输入
h = int(input())
m = int(input())
courses = []
for _ in range(m):
    s, c = map(float, input().split())
    courses.append([s, c])

# 输出
print(f"{max_gpa_increase(h, courses):.1f}")

22491: 冲刺GPA的贪心之路 ​

22491: 冲刺GPA的贪心之路