奖学金贪心求和

向右看齐 2022-07-16 03:59 157阅读 0赞

奖学金

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

## 题目描述 ##

小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

##### 输出描述: #####

一行输出答案。

##### 输入例子: #####

5 10 9
    0 5
    9 1
    8 1
    0 1
    9 100

##### 输出例子: #####

不知怎么回事下面的一直只通过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);
        	}
    
        }
    }

[Link 1]: http://www.nowcoder.com/questionCenter?questionTypes=000100&mutiTagIds=593
[Link 2]: http://www.nowcoder.com/courses/1