蓝桥杯【答疑】

题目描述

分析

这是一个贪心算法，要所得的时刻之和最小，而且下一个同学需要等上一个同学结束以后才能进行，因此需要对所耗总时间进行有小到大的排序，总时间相同的同学则对前两步时间之和有小到大进行排序，最后算出时间之和即可。

代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Tset {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Stu[] stu = new Stu[n];
        for(int i=0;i<n;i++){
            stu[i] = new Stu(scan.nextInt(),scan.nextInt(),scan.nextInt());
        }
        scan.close();
        Arrays.sort(stu, new Comparator<Stu>(){//自己定义一个比较器进行比较
            @Override
            public int compare(Stu o1,Stu o2) {//比较返回1,o1放后面，返回2，o2放后面
                if(o1.all-o2.all>0){
                    return 1;
                } else if (o1.all-o2.all<0) {
                    return -1;
                } else if (o1.two>=o2.two) {
                    return 1;
                }else {
                    return -1;
                }
            }
        });
        long min=0,time=0;//注意要使用long型，不然结果会超出
        for(int i=0;i<n;i++){
            min+=stu[i].s+stu[i].a+time;
            time+=stu[i].all;
        }
        System.out.println(min);
    }
}
//Stu类，用于储存n个学生的信息
class Stu{
    int s;
    int a;
    int e;
    int two;
    int all;
    Stu(int s,int a,int e){
        this.s = s;
        this.a = a;
        this.e = e;
        two = s+a;
        all = s+a+e;
    }
}

代码分析

在该段代码中，最重要的是使用了java.util.Comparator中的接口，并重写了int compare(T o1,T o2)方法，对o1,o2进行比较并排序，返回1时o1放在o2后，反之放在o2前。

来源：https://www.cnblogs.com/KJplant/p/17266545.html
本站部分图文来源于网络，如有侵权请联系删除。