首页 > 试题广场 >

奖学金

[编程题]奖学金
  • 热度指数:45798 时间限制: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分,已经达到拿奖学金的最低要求,所以可以不用复习。   
/*(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)
//需要说的一点是,存储总时间不能用int型的变量,要用long的,要不然有些大例子会使结果越界
//题目说的是动态规划,其实用的是贪心算法,而且是最简单的贪心:先用用时少的课程,如果无法
//达到总分,继续用用时次少的课程
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
bool cmp(const pair<int, int> p1, const pair<int, int> p2)
{
return p1.second < p2.second;
}
int main()
{
int n, r, avg;
while (cin>>n>>r>>avg)
{
vector<pair<int, int>> vec;
int a = 0;
int b = 0;
for (int i = 0; i < n;++i)
{
cin >> a >> b;
vec.push_back(make_pair(a, b));
}
//按照b的大小排序
sort(vec.begin(), vec.end(), cmp);
//相差的分数
int nDvalue = 0;
for (auto val : vec)
{
nDvalue += (avg-val.first);
}
//需要的总时间
long long nAllTime = 0;
//从成本最小的一门课开始
for (int index = 0; index<n&&nDvalue>0;++index)
{
int temp = r - vec[index].first;
if (nDvalue > temp)
{
nAllTime += vec[index].second*temp;
nDvalue -= temp;
}
else
{
nAllTime += vec[index].second*nDvalue;
nDvalue = 0;
}
}
cout << nAllTime << endl;
}
return 0;
}
发表于 2016-06-23 16:06:50 回复(3)
//老哥们,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();
	}
}

这题使用贪心即可,切记,计算时间的类型一定要用long,否则会有一个用例越界导致答案错误。
发表于 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)