【算法】学习与时间（贪心算法）-java

一、问题

小明是一名大学生，这个学期他有n门课程，每门课程都有考试，满分100，为了得到奖学金，小明需要保证所有课程60分及格，并达到制定的平均分avg（大于等于60分）。某门课编号i若想多得1分需花费ti的时间来复习考试，如不花费时间就为0分。已知每门课都平时成绩占30%，考试成绩占70%，求小明为了拿到奖学金最少需要花费多少时间在考试复习上。（注：会出现小数的数据全程用double类型）

二、要求

输入格式:
第1行为一个整数n，表示有n门课程。以下n行表示每门课程的平时成绩和多得1分花费时间，最后一行为奖学金设定的平均分。

输出格式:
输出小明最少花费复习的时间（double类型，保留两位小数）。

输入样例:
在这里给出一组输入。例如：
3
60 3
80 2
70 5
70

输出样例:
在这里给出相应的输出。例如：
647.14

三、代码

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
        static class Node{
                double peaceTime;
                double reviewTime;
                double basis;

                public double getPeaceTime() {
                        return peaceTime;
                }

                public void setPeaceTime(double peaceTime) {
                        this.peaceTime = peaceTime;
                }

                public double getReviewTime() {
                        return reviewTime;
                }

                public void setReviewTime(double reviewTime) {
                        this.reviewTime = reviewTime;
                }

                public double getBasis() {
                        return basis;
                }

                public void setBasis(double basis) {
                        this.basis = basis;
                }

        }

        //比较排序 平时成绩和多得1分花费时间 从小到大排序
        public static void compare(ArrayList<Node> list){
                Collections.sort(list,new Comparator(){
                        @Override
                        public int compare(Object o1, Object o2) {
                                Node node1=(Node)o1;
                                Node node2=(Node)o2;
                                if(node1.reviewTime>node2.reviewTime){
                                        return 1;
                                }else if(node1.reviewTime==node2.reviewTime){
                                        return 0;
                                }else{
                                        return -1;
                                }
                        }
                });
        }

        //计算所有的加权平时分 平时分*0.3
        public static double BaseValue(ArrayList<Node> list,double n){
                double BaseValue=0;
                for (int i = 0; i < n; i++) {
                        BaseValue+=list.get(i).getPeaceTime()*0.3;
                }
                return  BaseValue;
        }

        //计算正常总分60分时 不加权卷面分之和
        public  static  double passing(ArrayList<Node> list,double n){
                double difference=0;
                for (int i = 0; i < list.size(); i++) {
                        list.get(i).setBasis((60-list.get(i).peaceTime*0.3)/0.7);
                        difference+=(60-list.get(i).peaceTime*0.3)/0.7;
                }
                ;
                return difference;
        }

        //计算学习时间
        public static double spend(double avg,double n,ArrayList<Node> list) {
                compare(list);
                double time=0;//学习时间
                double totalScore=avg*n;//符合奖学金的制定的总分
                double baseValue=BaseValue(list,n);//所有的加权平时分
                double totalMark=(totalScore-baseValue)/0.7;//达到符合奖学金时的的卷面总分
                double difference=totalMark-passing(list,n);//卷面分差  =达到符合奖学金时的的卷面总分-及格时卷面总分
                //当所有科目总分是60分时所花时间
                for (int i = 0; i < list.size(); i++) {
                        time+=list.get(i).reviewTime*list.get(i).basis;
                }
                //如果卷面分差为0 则不需要在复习了
                if(difference<=0){
                        return time;
                }
                //复习
                for (int i = 0; i < list.size(); i++) {
                        //当前科目差多少分满分 是否 大于 卷面分差
                        if(100-list.get(i).basis>difference){ //是 那就学这一课就够了
                                time+=difference*list.get(i).reviewTime;//学习时长 =卷面分差*多得1分花费时间
                                difference-=difference;//将卷面分差清零
                        }else {
                                time+=(100-list.get(i).basis)*list.get(i).reviewTime;//学习时长 =满分与及格分差*多得1分花费时间
                                difference-=100-list.get(i).basis;//将卷面分减去-满分与及格分差
                        }
                }
                return time;
        }
        
        public static void main(String[] args) {
                ArrayList<Node> list=new ArrayList<>();
                Scanner scanner=new Scanner(System.in);
                int n=Integer.valueOf(scanner.nextLine());
                for (int i = 0; i < n; i++) {
                        String str=scanner.nextLine();
                        String[] ss=str.split(" ");
                        Node node=new Node();
                        node.setPeaceTime(Integer.valueOf(ss[0]));
                        node.setReviewTime(Integer.valueOf(ss[1]));
                        list.add(node);
                }
                String abg=scanner.nextLine();
                int avg=Integer.valueOf(abg);
                double spend = spend(avg,n,list);
                System.out.print(String.format("%.2f", spend));
        }
}