小v今年有 
门课，每门都有考试，为了拿到奖学金，小v必须让自己的平均成绩至少为
。
每门课由平时成绩和考试成绩组成，满分为 
。
现在他知道每门课的平时成绩为
,若想让这门课的考试成绩多拿一分的话，小v要花 
的时间复习，不复习的话当然就是0分。
同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金，小v至少要花多少时间复习。
[编程题]奖学金
/*(c/c++)
只需满足平均成绩大于等于avg即可，不管单科成绩。
所以先从花时间最少的课开始复习，使其满分。
伪码：
if(当前成绩 >= avg*n)
cout << 0 << endl;
else{
sort(时间花费)；
for（时间花费从小到大）
if 当前课程满分后不能获得奖学金
复习至满分，累加复习时间，然后复习下一门
else if 当前课程满分后能获得奖学金
所需时间 += （所需总分 - 当前分数）*在该课程上获得1分所需时间
输出时间；
退出循环。
}
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct score_hour
{
int score;
int hour;
};
bool cmp(score_hour a, score_hour b)
{
return a.hour < b.hour;
}
int main()
{
int n,r,avg;
while(cin >> n >> r >> avg){
vector<score_hour> v;
score_hour tmp;
while(n--){
cin >> tmp.score >> tmp.hour;
v.push_back(tmp);
}
int target = v.size()*avg;
int score_cur = 0;
long time = 0;
for(int i=0; i<v.size(); ++i){
score_cur += v[i].score;
}
if(score_cur>=target)
cout << 0 << endl;
else{
sort(v.begin(),v.end(),cmp);
for(int i=0; i<v.size(); ++i){
//该课程如果获得满分，求当前总分数
score_cur += (r - v[i].score);
if(score_cur >= target){
//当前分数超过目标成绩说明该课程不得满分也可满足奖学金条件
score_cur -= (r - v[i].score);
time += (target - score_cur)*v[i].hour;
cout << time << endl;
break;
}
else{
time += (r - v[i].score)*v[i].hour;
}
}
}
}
return 0;
}
编辑于 2016-03-20 17:06:53
回复(14)
//老哥们，40%是因为没有检测一开始就不用复习的，直接输出0就行。
//90%是数据范围太大了，使用long兴变量
import java.util.*;
public class Main{
public static void main(String[] args){
// int a = 1240 * 85;
// System.out.println(a);
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int r = sc.nextInt();
int avg = sc.nextInt();
long time = 0;
long total = 0;
List<cc> list = new ArrayList<cc>();
for(int i=0; i<n ;i++){
long ai = sc.nextLong();
total += ai;
list.add(new cc(ai,sc.nextLong()));
// System.out.println(i);
}
total = n*avg - total;
if(total <=0){
System.out.println(0);
continue;
}
Comparator<cc> c = new Comparator<cc>(){
public int compare(cc c1, cc c2){
if(c1.bi <= c2.bi){
return -1;
}else{
return 1;
}
}
};
Collections.sort(list,c);
for(int i=0; i<list.size(); i++){
cc ctemp = list.get(i);
if(total <=r - ctemp.ai){
time += total*ctemp.bi;
break;
}else{
time += (r-ctemp.ai)*ctemp.bi;
total -= r-ctemp.ai;
}
}
System.out.println(time);
}
}
}
class cc{
long ai;
long bi;
public cc(long ai, long bi){
this.ai = ai;
this.bi = bi;
}
}
发表于 2017-03-23 10:29:06
回复(5)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {//注意while处理多个case
int n = in.nextInt();
long r = in.nextLong();
long avg = in.nextLong();
long[][] arr = new long[n][2];
long total = avg*n;//需要的分数
long score = 0;//现在的分数
for(int i = 0;i<n;i++){
arr[i][0] = in.nextLong();//平时成绩
arr[i][1] = in.nextLong();//时间
score += arr[i][0];
}
sort(arr);
long time = 0;
int i = 0;
while(score<total&&i<n){
if(arr[i][0]<r){
//第i门课没有满分
time += arr[i][1];
score++;
arr[i][0] += 1;
}else{
i++;
}
}
System.out.println(time);
}
in.close();
}
//对时间进行排序
public static void sort(long[][]a){
for(int i = 0;i<a.length-1;i++){
boolean flag = true;
for(int j = 0;j<a.length-1-i;j++){
if(a[j][1]>a[j+1][1]){
long temp = a[j][0];
long temp2 = a[j][1];
a[j][0] = a[j+1][0];
a[j+1][0] = temp;
a[j][1] = a[j+1][1];
a[j+1][1] = temp2;
flag = false;
}
}
if(flag)
return;
}
}
}
发表于 2016-04-10 16:25:00
回复(5)
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static class Score {
int a;
int b;
int current;
public Score(int a, int b) {
this.a = a;
this.b = b;
this.current = a;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
PriorityQueue<Score> priorityQueue = null;
while (scanner.hasNextInt()) {
int n = scanner.nextInt();
int full = scanner.nextInt();
int avg = scanner.nextInt();
int total = n * avg;
priorityQueue = new PriorityQueue<Score>(n, new Comparator<Score>() {
@Override
public int compare(Score o1, Score o2) {
if (o1.b == o2.b)
return 0;
else if (o1.b > o2.b)
return 1;
else
return -1;
}
});
for (int i = 0; i < n; ++i) {
int a = scanner.nextInt();
int b = scanner.nextInt();
total -= a;
Score score = new Score(a, b);
priorityQueue.add(score);
}
long needTime = 0;
while (!priorityQueue.isEmpty() && total > 0) {
Score score = priorityQueue.remove();
int tmp = full - score.a;
if (total < tmp) {
tmp = total;
}
score.current = full;
total -= tmp;
needTime += tmp * score.b;
}
System.out.println(needTime);
}
scanner.close();
}
}
发表于 2016-08-30 10:58:59
回复(4)
【397 104 98】的这个案例始终通不过，为什么？求解！
import java.util.*;
import java.util.stream.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(System.in);
// 科目数量
int count = scan.nextInt();
// 满分
int full = scan.nextInt();
// 平均分
int avg = scan.nextInt();
List<AB> list = new ArrayList<>();
while(list.size() != count) {
int a = scan.nextInt();
int b = scan.nextInt();
list.add(new AB(a, b));
}
scan.close();
System.out.print(time(count, full, avg, list));
}
public static long time(int count, int full, int avg, List<AB> list) {
// 按b排序
List<AB> list2 = list.stream().sorted(Comparator.comparing(AB::getB)).collect(Collectors.toList());
// 总缺的分数
int less = (avg * count) - list2.stream().map(AB::getA).reduce(0, Integer::sum);
// 总复习时间
long time = 0;
for (AB ab : list2) {
// 本门课离满分的数
int lessScore = full - ab.getA();
// 如果分数不够，继续复习
if (lessScore < less) {
time += lessScore * ab.getB();
less -= lessScore;
}
// 如果学完这门课就够了，学够时间停止复习
else {
time += less * ab.getB();
break;
}
}
return time;
}
static class AB {
private Integer a;
private Integer b;
public AB(int a, int b) {
this.a = a;
this.b = b;
}
public Integer getA() {
return a;
}
public Integer getB() {
return b;
}
}
}
发表于 2020-08-06 10:52:49
回复(0)
//直接使用贪心算法，对容器vector按提高一分所花费的时间从小到大排序，然后将 //花费少的先学到满分，判断当前总分是否满足平均分要求，满足要则计算学到目标 //分花费的时间；如果还不够，则继续学习下一门课程。 //注意：此题的测试用例采用了循环输入测试，所以要采用while循环！！！之前没采 //用while循环，一直通不过，弄了大半天找原因！！！
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(const pair<int, int> &a, const pair<int, int> &b){
return a.second < b.second;
}
int main(){
int n, r, avg;
while (cin >> n >> r >> avg){
vector<pair<int, int>> vec;
for (int i = 0; i<n; i++){
int x, y;
cin >> x >> y;
vec.push_back({ x, y });
}
int sum = 0;
int target = n*avg;
//求当前的总分
for (auto i : vec){
sum += i.first;
}
long time = 0;
if (sum >= target){
cout << time << endl;
}
else{
sort(vec.begin(), vec.end(), cmp);
for (int i = 0; i < n; i++){
int temp = r - vec[i].first;
//当前课程学到满分，是否满足目标分数要求
if (sum + temp >= target){ //满足
time += (target - sum)*vec[i].second;
sum = target;
break;
}
else{ //不满足
sum += temp;
time += temp*vec[i].second;
}
}
cout << time << endl;
}
}
return 0;
}
编辑于 2018-03-17 14:01:53
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct score_hour
{
int score;
int hour;
score_hour(int ai, int bi){
score = ai;
hour = bi;
}
};
// for sort
bool cmp(score_hour a, score_hour b)
{
return a.hour < b.hour;
}
int main(){
// for store ai and bi
vector<score_hour> vec;
// for store input
int n, r, avg;
cin >> n >> r >> avg;
// store input ai and bi
for (int i = 0; i < n; i++){
int ai, bi;
cin >> ai >> bi;
score_hour* tmp = new score_hour(ai, bi);
vec.push_back(*tmp);
}
// for debug
// cout << vec[0].score << vec[0].hour << endl;
sort(vec.begin(), vec.end(), cmp);
// need scores
int need_points = 0;
for (int i = 0; i < vec.size(); i++)
{
need_points += (avg - vec[i].score);
}
//std:: cout << "need_pints:" << need_points << endl;
// at least need review hours
int need_hours = 0;
for (int i = 0; i < vec.size() && need_points > 0; i++){
if (vec[i].score < r){
int tmp = r - vec[i].score;
if (tmp > need_points){
need_hours += need_points*vec[i].hour;
need_points = 0;
}
else{
need_hours += tmp * vec[i].hour;
// std::cout << "need_ hours:" << need_hours << endl;
need_points -= tmp;
}
}
// std:: cout << "need_pints:" << need_points << endl;
}
std::cout << need_hours << endl;
// std::system("pause");
return 0;
}
发表于 2015-10-08 19:11:21
回复(7)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int n = scan.nextInt();
int r = scan.nextInt();
int avg = scan.nextInt();
List<Course> list = new ArrayList<Course>(n);
int score = 0;
int a,b;
for(int i=0; i<n; i++){
a = scan.nextInt();
b = scan.nextInt();
score += a;
list.add(new Course(a, b));
}
Collections.sort(list);
int i=0, j=0;////i 表示复习得分
int needScore = avg*n-score;
long time = 0;
while(i < needScore){
while(i<needScore && list.get(j).grade < r){
time += list.get(j).time;
list.get(j).grade++;
i++;
}
if(i < needScore)
j++;
}
System.out.println(time);
}
}
}
class Course implements Comparable<Course>{
int grade;
int time;
public Course(int grade, int time){
this.grade = grade;
this.time = time;
}
public int compareTo(Course arg){
return this.time-arg.time;
}
}
发表于 2017-08-15 10:30:18
回复(0)
之前总是通过95%，后来发现时间time的类型有问题，int型会溢出，转用long就可以通过。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Ai_bi{
int ai;
int bi;
};
bool compare(Ai_bi a1, Ai_bi a2)
{
return a1.bi < a2.bi;
}
int main()
{
int n, r, avg;
while (cin >> n >> r >> avg)
{
vector<Ai_bi> ab(n);
for (int i = 0; i < n; i++)
cin >> ab[i].ai >> ab[i].bi;
int targ = n*avg;
int temp = 0;
for (auto i : ab)
temp += i.ai;
temp = targ - temp;//还需要多少分
long time = 0;
sort(ab.begin(), ab.end(), compare);
for (int i = 0; temp>0&&i < n;i++)
{
int res = r - ab[i].ai;
if (res < temp)
{
temp -= res;
time += ab[i].bi*res;
}
else
{
time += ab[i].bi*temp;
temp = 0;
break;
}
}
if (temp>0)
cout << "error!" << endl;
else
cout << time << endl;
}
return 0;
}
发表于 2017-08-06 23:09:58
回复(0)
// 大致思路就是先复习花费代价最小的课程，因此需要根据bi对其进行一个升序排序
// 然后计算所有课程达到平均分的情况下，还需要在平时成绩的基础上得到多少分
// 最后根据这个需要得到的分数 needed去将队列中的课程按代价递增的顺序依次修到满分，直到修够needed分
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
public static void main(String[] args) {
java.util.Scanner cin = new java.util.Scanner(System.in);
while(cin.hasNext()){
int n, r, avg;
n = cin.nextInt();
r = cin.nextInt();
avg = cin.nextInt();
List<Pair> scoreQueue = new ArrayList<Pair>();
int needed = 0;
int aSum = 0;
int a = 0, b = 0;
for(int i=0; i<n; i++){
a = cin.nextInt();
aSum += a;
b = cin.nextInt();
scoreQueue.add(new Pair(a, b));
}
needed = n * avg - aSum;
//cin.close();
// System.out.println(needed);
Collections.sort(scoreQueue);
long timeSum = 0;
int getted = 0;
for(int i=0; i<scoreQueue.size(); i++){
if((getted + r - scoreQueue.get(i).a) < needed){
timeSum += (r - scoreQueue.get(i).a) * scoreQueue.get(i).b;
getted += (r - scoreQueue.get(i).a);
}else{
if(getted < needed){
timeSum += (needed - getted) * scoreQueue.get(i).b;
break;
}
}
}
System.out.println(timeSum);
}
cin.close();
}
static class Pair implements Comparable<Pair>{
int a;
int b;
public Pair(int a, int b){
this.a = a;
this.b = b;
}
@Override
public int compareTo(Pair o) {
if(this.b > o.b) return 1;
if(this.b < o.b) return -1;
return 0;
}
}
}
发表于 2016-08-07 10:58:44
回复(3)
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int r=in.nextInt();
int avg=in.nextInt();
int a=0,b=0;
Map<Integer,Integer> map=new TreeMap<Integer,Integer>();
int pin=0;//平时总成绩
for(int i=0;i<n;i++){
a=in.nextInt();
pin+=a;
b=in.nextInt();
if(map.get(b)!=null){
map.put(b,map.get(b)+r-a);
}else{
map.put(b,r-a);
}
}
int sum=avg*n;//要拿奖学金成绩
int xu=sum-pin;//需要的考试成绩
Set<Integer> set=map.keySet();
int res=0;//记录结果
int index=0;
for(Integer e:set){
index=map.get(e);
if(index<=xu){
res+=index*e;
xu-=index;
}else{
res+=e*xu;
break;
}
}
System.out.println(res);
in.close();
}
}
编辑于 2015-10-10 12:23:21
回复(15)
贪心
先排序，把复习起来轻松的排在前面，优先复习这些课程。顺序遍历排序后的课程表，如果总分不小于avg*n了就停止复习。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
while((line = br.readLine()) != null){
String[] params = line.split(" ");
int n = Integer.parseInt(params[0]);
int r = Integer.parseInt(params[1]);
int avg = Integer.parseInt(params[2]);
int[][] scores = new int[n][2];
int base = 0; // 平时总成绩，作为基础得分
for(int i = 0; i < n; i++){
String[] pair = br.readLine().split(" ");
scores[i][0] = Integer.parseInt(pair[0]);
scores[i][1] = Integer.parseInt(pair[1]);
base += scores[i][0];
}
Arrays.sort(scores, (a, b) -> a[1] - b[1]); // 把复习起来最轻松的排在前面
System.out.println(solve(n, r, avg, scores, base));
}
}
private static long solve(int n, int r, int avg, int[][] scores, int base) {
long timeConsuming = 0;
for(int i = 0; i < n && n*avg > base; i++){
int time = Math.min(r - scores[i][0], n*avg - base); // 课程得分不能超过满分
timeConsuming += time * scores[i][1];
base += time;
}
return timeConsuming;
}
}
发表于 2022-01-13 12:13:58
回复(0)
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)
还是挺简单的，关键是输入语法和排序的问题。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNextInt()){
int n = in.nextInt();
int r = in.nextInt();
int avg = in.nextInt();
long totleScore = n * avg, baseScore = 0;
int[][] arr = new int[n][2];
for(int i = 0; i < n; i++){
arr[i][0] = in.nextInt();
arr[i][1] = in.nextInt();
baseScore += arr[i][0];
}
long restScore = totleScore - baseScore;
Arrays.sort(arr, (o1, o2)->
{return o1[1] - o2[1] == 0? o1[0] - o2[0]:o1[1] - o2[1];});
long ans = 0;
for(int i = 0; i < n; i++){
while(arr[i][0] < r && restScore > 0){
arr[i][0]++;
restScore--;
ans += arr[i][1];
}
if(restScore < 0)
break;
}
System.out.println(ans);
}
}
}
发表于 2021-08-24 14:55:51
回复(0)
//简单贪心，优先成本低的加分
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
using ll = long long;
pair<int, int> a[N];
int main() {
int n, r, arg;
while (cin >> n >> r >> arg) {
ll target = arg * n;
for (int i = 0; i < n; ++i) {
cin >> a[i].second >> a[i].first;
target -= a[i].second;
}
if (target <= 0) {
cout << 0 << endl;
continue;
}
ll ans = 0;
sort(a, a + n);
for (int i = 0; i < n && target > 0; ++i) {
if (target >= r - a[i].second) {
ans += (ll)(r - a[i].second) * (ll)a[i].first;
} else {
ans += (target * a[i].first);
}
target -= (r - a[i].second);
}
cout << ans << endl;
}
return 0;
}
发表于 2021-04-03 18:13:46
回复(0)
const readline = require('readline'), rl = readline.createInterface(process.stdin, process.stdout);
let n, r, avg, arr = [], count = 0;
rl.on('line', function(line) {
if (n == undefined) {
[n, r, avg] = line.trim().split(' ');
n = +n, r = +r, avg = +avg;
count = n, arr = [];
} else {
if (count > 0) {
let temp = line.trim().split(' ')
arr.push([+temp[0], +temp[1]]);
count--;
}
if(count == 0) {
let res = fun(n, r, avg, arr)
console.log(res);
n = undefined;
}
}
})
var fun = function(n, r, avg, arr) {
let need = n * avg, time = [], res = 0;
for (let i = 0; i < n; i++) {
need -= arr[i][0];
time.push([r-arr[i][0], arr[i][1]]);
}
if (need <= 0) return 0;
time.sort((a, b)=>(a[1] - b[1]));
// console.log(need, time)
for (let i = 0; i < n; i++) {
if (time[i][0] < need) {
res += time[i][1]*time[i][0];
need -= time[i][0];
} else {
res += time[i][1] * need;
break;
}
}
return res;
} 贪心算法，总选择最小代价得的分数。先写好输入输出流（太蹩脚了），注意无需复习的情况。
发表于 2021-03-29 10:51:16
回复(0)
利用贪心算法就可解出来，只不过要排除加完所有基本分已经达到平均分的情况。然后数据用long保存即可。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class WY1 {
static class Obj {
int a;
int b;
public Obj(int a, int b) {
this.a = a;
this.b = b;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int r = sc.nextInt();
int avg = sc.nextInt();
long idealScore = n*avg;
long time = 0;
List list = new ArrayList();
for(int i = 0; i < n; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
list.add(new Obj(a, b));
idealScore -= a;
}
if(idealScore <= 0) {
System.out.println(0);
continue;
}
list.sort((Obj o1, Obj o2) -> o1.b - o2.b);
for (Obj o:list) {
if(o.a >= r)
continue;
if(idealScore - (r-o.a) > 0) {
idealScore -= (r-o.a);
time += (r-o.a)*o.b;
}else {
time += idealScore*o.b;
break;
}
}
System.out.println(time);
}
}
}
编辑于 2020-08-07 19:25:11
回复(0)
凭着感觉写，第一次没考虑时间溢出。。。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int nCount, nMax, nAve;
while (cin >> nCount >> nMax >> nAve)
{
vector<pair<int, int>> vecData(nCount);
int nRest = nCount * nAve;
long nTime = 0;
for (int i = 0; i < nCount; ++i)
{
cin >> vecData[i].second >> vecData[i].first;
nRest -= vecData[i].second;
}
sort(vecData.begin(), vecData.end());
auto iter = vecData.begin();
while (nRest > 0 && iter != vecData.end())
{
nTime += ((nMax - iter->second) * iter->first);
nRest -= (nMax - iter->second);
if (nRest < 0)
nTime -= (-nRest) * iter->first;
++iter;
}
cout << nTime << endl;
}
}
发表于 2019-08-26 17:00:30
回复(0)
import java.util.*;
class Course{
int ai;
int bi;
int remainScore;
}
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int r=sc.nextInt();
int avg=sc.nextInt();
ArrayList<Course> arrayList=new ArrayList<Course>();
int totalScore=0;
for(int i=0;i<n;i++){
Course course=new Course();
course.ai=sc.nextInt();
course.bi=sc.nextInt();
course.remainScore=r-course.ai;
arrayList.add(course);
totalScore+=course.ai;
}
Collections.sort(arrayList,new Comparator<Course>(){
public int compare(Course course1,Course course2){
if(course1.bi>course2.bi)
return 1;
else if(course1.bi<course2.bi)
return -1;
return 0;
}
});
int reachScore=avg*n;
if(totalScore>reachScore){
System.out.println(0);
continue;
}
double result=0;
for(int i=0;i<n;i++){
if(reachScore-totalScore>arrayList.get(i).remainScore){
result+=arrayList.get(i).remainScore*arrayList.get(i).bi;
totalScore+=arrayList.get(i).remainScore;
}else{
result+=(reachScore-totalScore)*arrayList.get(i).bi;
break;
}
}
System.out.printf("%.0f",result);
System.out.println();
}
}
}
发表于 2018-10-12 20:37:14
回复(0)
package com.special.improve;
import java.util.Scanner;
/**
* 网易01-奖学金
*
* 思路：贪心算法，我实在不知道动态规划怎么做哦
*
* 1.首先我们要明确要想平均分达到指定值，那么也就是说总分必须多少
* 这样我们只需再获得总分 - 已获得分数 即可得到奖学金
* 2.我们采用贪心的算法，每次都优先学花费时间少的科目，直到它满分或者已达到指定分数即可
* 3.若第2部没有结束，继续在剩下的科目里找到次花费少的，继续第二步即可
*
* 注意：time可能非常大，所以用long代替int
*
* 优化：我们可以事先对科目的花费时间排序，只需按需学习即可，而不用每次都找出最小值了
* Create by Special on 2018/3/5 13:50
*/
public class Pro041 {
public static long getMinCostTime(int n, int r, int needGrade, int[] usualGrade, int[] costTime){
long time = 0;
int min, index = 0, diss;
boolean[] visited = new boolean[n];
while(needGrade > 0){
min = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
if(!visited[i] && costTime[i] < min){
index = i;
min = costTime[i];
}
}
visited[index] = true;
diss = Math.min(r - usualGrade[index], needGrade);
time += diss * costTime[index];
needGrade -= diss;
}
return time;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int n = input.nextInt();
int r = input.nextInt();
int avg = input.nextInt();
int[] usualGrade = new int[n];
int[] costTime = new int[n];
int needGrade = 0;
for(int i = 0; i < n; i++){
usualGrade[i] = input.nextInt();
costTime[i] = input.nextInt();
needGrade += usualGrade[i];
}
needGrade = n * avg - needGrade;
System.out.println(getMinCostTime(n, r, needGrade, usualGrade, costTime));
}
}
}
发表于 2018-03-05 14:37:04
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-02 15:32:56 -
2022-10-10 16:44:47 -
2022-09-13 18:54:44
-
2022-09-13 18:07:40 -
2022-09-13 13:18:03
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
