首页 > 试题广场 >

奖学金

[编程题]奖学金
  • 热度指数：45661 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小v今年有n门课，每门都有考试，为了拿到奖学金，小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成，满分为r。在考试前，小v他已经知道每门课的平时成绩为ai ，假设付出的时间与获得的分数成正比，若想让这门课的考试成绩多拿一分的话，小v要花bi 的时间复习，不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。问小v为了拿到奖学金，至少要花多少时间复习？

输入描述:
第一行三个整数n,r,avg（1 <= n <= 105，1 <= r <= 109，1 <= avg <= 106），接下来n行，每行两个整数ai和bi，（0 <= ai <= 106，1 <= bi <= 106）

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


输出描述:
每个用例对应一行输出答案。
示例1

输入

5 10 9
0 5
9 1
8 1
0 1
9 100
3 5 3
2 1
4 100
3 3

输出

43
0

说明

示例1有两组测试用例。
对于第2组测试用例，小v的平时成绩的平均成绩为(2+4+3)/3=3分，已经达到拿奖学金的最低要求，所以可以不用复习。
算法知识视频讲解
开通博客
头像 Jevin_yao
发表于 2020-08-07 17:07:12
解题思路： 根据输入的每门课程对可能提分所需要的时间进行从小到大的排序，因为后面需要得出花费的最少复习时间，所以要先把能花时间少的提分科目提到满分; 使用一个TreeSet实现排序，因为TreeSet对整型数据有自动排序功能，而且可以去重; 将提升花费时间作为key,科目目前还可以得到的分数作为v 展开全文
去ta的博客 赞 (15) 回复(0) 收起
头像 hyandsg
发表于 2021-01-31 10:03:18
大概思路：遇到极值问题一般想到贪心解决，这里很容易想到按课程复习代价从小到大排序，贪心的证明用反证法证明即可。个人踩雷：1 输入有多个测试样例，需要Scanner.hasNext();2 看测试数据的范围，可以看出int不够大，需要使用long。 import java.util.*; public 展开全文
去ta的博客 赞 (12) 回复(0) 收起
头像 摆烂摆烂摆烂
发表于 2022-05-09 17:17:25
if __name__ == '__main__': while True: nravg = sys.stdin.readline().strip() if not nravg: break n,r,avg = [int 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客499819205号
发表于 2021-10-15 17:24:02
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool compare(const&nbs 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 climax_
发表于 2023-03-30 18:52:32
#include <iostream> using namespace std; int main() { long long r,avg,min_score,flag_a,flag_b,n; while(cin>>n>>r>>avg 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 climax_
发表于 2023-03-30 18:53:46
#include <iostream> using namespace std; int main() { long long r,avg,min_score,flag_a,flag_b,n; while(cin>>n>>r>>avg 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客898423844号
发表于 2021-09-15 20:45:31
#include<iostream> #include<vector> using namespace std; struct cla //课程 { int s; //分数 int t; //时间 }; long long plan(vect 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 👉爱🌹如流水👈
发表于 2021-04-19 17:19:25
贪心策略：第一步：计算已经取得成绩第二步：计算每门最大可以还可以获得多少分第三步: 计算还需取得成绩P第四步：按照升序排序第五步：从小往大取 并注意受限条件。 #include<iostream> using namespace std; #include<vector> # 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客660479076号
发表于 2022-04-28 20:42:01
import java.util.*; public class Main{ public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.has 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客409434554号
发表于 2022-01-05 15:04:50
">using namespace std; struct xk{ int a,b; }; bool cmp(xk &x,xk &y) { return x.b<y.b; } int main() { int n,r,avg; while(cin 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 模拟
来自：网易2016校招研发工...
难度：
242条回答 36104浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号