奖学金贪心求和

112 阅读 0 评论 74 点赞

我是靠谱客的博主受伤星星，最近开发中收集的这篇文章主要介绍奖学金贪心求和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

奖学金

热度指数：2143时间限制：1秒空间限制：32768K
本题知识点：动态规划
算法知识视频讲解

题目描述

小v今年有n门课，每门都有考试，为了拿到奖学金，小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成，满分为r。现在他知道每门课的平时成绩为a i ,若想让这门课的考试成绩多拿一分的话，小v要花b i 的时间复习，不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金，小v至少要花多少时间复习。

输入描述:

第一行三个整数n,r,avg(n大于等于1小于等于1e5，r大于等于1小于等于1e9,avg大于等于1小于等于1e6)，接下来n行，每行两个整数ai和bi，均小于等于1e6大于等于1

输出描述:

一行输出答案。

输入例子:

输出例子:

不知怎么回事下面的一直只通过40%，用贪心做的：

import java.util.*;

public class Main{
    public static void main(String[] args){
    	Scanner in = new Scanner(System.in);
    	while(in.hasNext()){
    		int n,r,avg;
        	n = in.nextInt();
        	r = in.nextInt();
        	avg = in.nextInt();
        	int[] a = new int[n];
        	int[] b = new int[n];
        	int[] v = new int[n];
        	int[] used = new int[n];
        	int tempsum=0;
        	for(int i=0;i<n;i++){
        		a[i] = in.nextInt();
        		tempsum+=a[i];
        		b[i] = in.nextInt();
        		v[i]=b[i];
        	}
        	int des = n*avg;
        	int time = 0;
        	Arrays.sort(v);
        	
        	for(int i=0;i<n;){
        		for(int j=0;j<n;j++){
        			if(b[j]==v[i]&&used[j]==0){
        				if(r-a[j]<des-tempsum){
        					tempsum+=r-a[j];
        					time += (r-a[j])*b[j];
        					i++;
        				}else if(r-a[j]==des-tempsum){
        					tempsum+=r-a[j];
        					time += (r-a[j])*b[j];
        					i++;
        					break;
        				}else{
        					int diff = des-tempsum;
        					tempsum += diff;
        					time += diff*b[j];
        					i++;
        					break;
        				}
        			    used[j]=1;
        			}
        		}
        	}
        	System.out.println(time);
    	}

    }
}

换了一种思路，用hashmap做，还是没有全ac，通过90%，按下面改正后AC。

思路：

通过一个hashmap存储下每个科目可以加的分数，直接把加相同分数的，加到hashmap的同一个value里。

对hashmap排序。

用贪心从头开始计算，与需要的分数相比较，如果小或等于就加上当前的科目可以下的分，同时计算时间。如果当前科目可以加的分大于需要的分数，按照需要的分数计算。

最后输出时间。

import java.util.*;

public class Main{
    public static void main(String[] args){
    	Scanner in = new Scanner(System.in);
    	while(in.hasNext()){
    		int n,r,avg;
        	n = in.nextInt();
        	r = in.nextInt();
        	avg = in.nextInt();
        	int[] a = new int[n];
        	int[] b = new int[n];
        	HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
        	int tempsum=0;
        	for(int i=0;i<n;i++){
        		a[i] = in.nextInt();
        		tempsum+=a[i];
        		b[i] = in.nextInt();
        		if(hm.containsKey(b[i])){
        			hm.put(b[i], hm.get(b[i])+r-a[i]);
        		}else{
        			hm.put(b[i], r-a[i]);
        		}
        	}
        	int des = n*avg;
        	int time = 0;

        	List<Map.Entry<Integer,Integer>> info = new ArrayList<Map.Entry<Integer,Integer>>(hm.entrySet());
        	Collections.sort(info,new Comparator<Map.Entry<Integer, Integer>>(){
        		public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2){
        			return o1.getKey().compareTo(o2.getKey());
        		}
        	});
        	for(int i=0;i<info.size();i++){
        		if(tempsum<=des){
        			if(info.get(i).getValue()<des-tempsum){
        				tempsum += info.get(i).getValue();
        				time += info.get(i).getValue()*info.get(i).getKey();
        			}else if(info.get(i).getValue()==des-tempsum){
        				tempsum += info.get(i).getValue();
        				time += info.get(i).getValue()*info.get(i).getKey();
        				break;
        			}else{
        				int diff = des-tempsum;
        				tempsum += diff;
        				time += diff*info.get(i).getKey();
        				break;
        			}
        		}
        	}
        	
        	System.out.println(time);
    	}

    }
}

后来终于发现了问题的原因，原来是 time（需要的时间）的变量需要用Long,不然用int有个测试用例会越界，所以改成long之后就AC了，好坑。，下面是AC的代码：

import java.util.*;

public class Main{
    public static void main(String[] args){
    	Scanner in = new Scanner(System.in);
    	while(in.hasNext()){
    		int n,r,avg;
        	n = in.nextInt();
        	r = in.nextInt();
        	avg = in.nextInt();
        	int[] a = new int[n];
        	int[] b = new int[n];
        	HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
        	int tempsum=0;
        	for(int i=0;i<n;i++){
        		a[i] = in.nextInt();
        		tempsum+=a[i];
        		b[i] = in.nextInt();
        		if(hm.containsKey(b[i])){
        			hm.put(b[i], hm.get(b[i])+r-a[i]);
        		}else{
        			hm.put(b[i], r-a[i]);
        		}
        	}
        	int des = n*avg;
        	long time = 0;   //改成long就ac了。。。好坑，因为int会越界，有一个测试用例过不去

        	List<Map.Entry<Integer,Integer>> info = new ArrayList<Map.Entry<Integer,Integer>>(hm.entrySet());
        	Collections.sort(info,new Comparator<Map.Entry<Integer, Integer>>(){
        		public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2){
        			return o1.getKey().compareTo(o2.getKey());
        		}
        	});
 
        	for(int i=0;i<info.size();i++){
        		if(tempsum<=des){
        			if(info.get(i).getValue()<des-tempsum){
        				tempsum += info.get(i).getValue();
        				time += info.get(i).getValue()*info.get(i).getKey();
        			}else if(info.get(i).getValue()==des-tempsum){
        				tempsum += info.get(i).getValue();
        				time += info.get(i).getValue()*info.get(i).getKey();
        				break;
        			}else{
        				int diff = des-tempsum;
        				tempsum += diff;
        				time += diff*info.get(i).getKey();
        				break;
        			}
        		}
        	}
        	
        	System.out.println(time);
    	}

    }
}