小v今年有n门课,每门都有考试,为了拿到奖学金,小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成,满分为r。现在他知道每门课的平时成绩为ai ,若想让这门课的考试成绩多拿一分的话,小v要花bi 的时间复习,不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金,小v至少要花多少时间复习。 输入描述 输入包含多个测试用例,每个测试用例的第1行为整数n(1<=n<=200),表示课程门数,接下来的n行,每行两个整数,分别表示一门课的平时成绩和b[i],最后一行输入满分r和希望达到的平均成绩avg。输入 n=0 结束 输出描述 每个测试用例输出一行,表示小v要花的最少复习时间。 输入样例 4 80 5 70 2 90 3 60 1 100 92.5 0
时间: 2024-03-27 19:39:41 浏览: 50
以下是 Python3 代码实现:
```python
while True:
n = int(input())
if n == 0:
break
scores = []
total_score = 0
for i in range(n):
a, b = map(int, input().split())
scores.append((a, b))
total_score += a
r, avg = map(int, input().split())
need_score = avg * n - total_score # 需要的考试总分
scores.sort(key=lambda x: x[1]) # 按复习时间从小到大排序
ans = 0 # 最少复习时间
for a, b in scores:
if need_score <= 0:
break
score = min(r - a, need_score) # 最多拿到的考试分数
ans += score * b
need_score -= score
print(ans)
```
算法思路:
首先,我们需要计算出小v需要在考试中获得的总分数,即 $need\_score=avg\times n-\sum_{i=1}^{n}{a_i}$。然后,将所有课程按复习时间从小到大排序,依次遍历每门课程,计算出最多能获得的考试分数 $score=\min(r-a_i, need\_score)$,并将复习时间乘以 $score$ 累加到答案中,最后输出答案即可。
时间复杂度为 $O(n\log n)$。
相关推荐
![none](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)