首页 > 试题广场 >

奖学金

[编程题]奖学金

热度指数：45798 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小v今年有n门课，每门都有考试，为了拿到奖学金，小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成，满分为r。在考试前，小v他已经知道每门课的平时成绩为a_i ，假设付出的时间与获得的分数成正比，若想让这门课的考试成绩多拿一分的话，小v要花b_i 的时间复习，不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。问小v为了拿到奖学金，至少要花多少时间复习？

输入描述:

第一行三个整数n,r,avg（1 <= n <= 10⁵，1 <= r <= 10⁹，1 <= avg <= 10⁶），接下来n行，每行两个整数a_i和b_i，（0 <= a_i <= 10⁶，1 <= b_i <= 10⁶）

注意：本题含有多组样例输入。

输出描述:

每个用例对应一行输出答案。

示例1

输入

输出

43
0

说明

示例1有两组测试用例。
对于第2组测试用例，小v的平时成绩的平均成绩为(2+4+3)/3=3分，已经达到拿奖学金的最低要求，所以可以不用复习。

算法知识视频讲解

Python3

牛客904429547号

while True:
    try:
        x = list(map(int, input().strip().split()))
        l = [[0]*2 for i in range(x[0])]
        for i in range(x[0]):
            tmp = list(map(int, input().strip().split()))
            l[i][0], l[i][1] = tmp[0], tmp[1]
        l = sorted(l,key=lambda x:x[1])
        total = x[0] * x[2]
        count, richang = 0, 0
        #  处理初始的日常分
        for i in range(x[0]):
            richang += l[i][0]
        if total <= richang:
                print(0)
                continue
        total -= richang
        i = 0
        while i < x[0]:
            if x[1] - l[i][0] <= total:
                total -= x[1]-l[i][0] 
                count += (x[1] - l[i][0] )* l[i][1]
                i += 1
                continue
            else:
                count += total *l[i][1]
                break
        print(count)
    except:
        break

发表于 2021-09-05 10:03:02 回复(0)