#yyds干货盘点# 解决名企真题： 奖学金

1.简述：

描述

小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分，已经达到拿奖学金的最低要求，所以可以不用复习。

2.代码实现：

import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int full=sc.nextInt();
int avg=sc.nextInt();
int[][] nums=new int[n][2];
for(int i=0;i<n;i++){
nums[i][0]=sc.nextInt();
nums[i][1]=sc.nextInt();
}
Arrays.sort(nums,(o1,o2)->o1[1]-o2[1]);//按复习代价从小到大排序
long sum=0;
for(int[] a:nums) {
sum+=a[0];
}
long limit=avg*n;
int index=0;
long time=0;
while(sum<limit){
int tmp=full-nums[index][0];
if(tmp+sum<=limit){ //如果一门课程复习到满分，小于限制，
time+=tmp*nums[index][1];
sum+=tmp;
index++;
}
else{ //如果一门课程复习到满分，大于限制，
time+=(limit-sum)*nums[index][1];
sum=limit;
}
}
System.out.println(time);
}
}
}