【蓝桥杯】历届真题 答疑（决赛）Java

【问题描述】
        有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。

        老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。

        一位同学答疑的过程如下：

        1.首先进入办公室，编号为 i 的同学需要 si 毫秒的时间。
        2.然后同学问问题老师解答，编号为 i 的同学需要 ai 毫秒的时间。
        3.答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。
        4.最后同学收拾东西离开办公室，需要 ei 毫秒的时间。一般需要 10 秒、20 秒或 30 秒，即 ei 取值为 10000，20000 或 30000。
        一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。

        答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群里面发消息的时刻之和最小。

【输入格式】
输入第一行包含一个整数 n，表示同学的数量。
接下来 n 行，描述每位同学的时间，其中第 i 行包含三个整数 si,ai,ei 意义如上所述。

【输出格式】
输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。

【样例输入】
3
10000 10000 10000
20000 50000 20000
30000 20000 30000

【样例输出】
280000

【样例说明】
        按照 1 , 3 , 2  的顺序答疑，发消息的时间分别是 20000 , 80000 , 180000 。

【评测用例规模与约定】
        对于 30% 的评测用例，1 ≤ n ≤ 20 
        对于 60% 的评测用例，1 ≤ n ≤ 200 
        对于所有评测用例,1 ≤ n ≤ 1000，1 ≤ s i ≤ 60000，1 ≤ a i ≤ 1000000 ，

e i ∈{10000 , 20000 , 30000}，即ei一定是10000、20000、30000之一。

【思路与分析】

        这道题目看起来复杂，其实很简单。就是一个很典型的贪心算法的题目。首先我们知道，前面的同学总用时要尽可能少。

        每个同学发送信息的时间其实都是所用时间的（n-i）倍。因此，前面的同学只需要总用时尽可能少就可以了。这个实现起来还是很简单的，录入时间，排序即可。

        那么在总用时排序之后，总用时相同的情况下比较s+a（也就是发出信息的时间）。在s+a再次相同的情况下，最后比较e的用时。

【代码】

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
	
	public static void main(String[] args) throws IOException {
        int n=0;
        int time[][] = new int[1005][2];
		StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		
		PrintWriter pr = new PrintWriter(new OutputStreamWriter(System.out));
		st.nextToken();
        n=(int)st.nval;
		
		for(int i=1;i<=n;i++) {
            //分别获取s、a、e的时间
			st.nextToken();
            int s=(int)re.nval;

			st.nextToken();
            int a=(int)re.nval;

			st.nextToken();
            int e=(int)re.nval;

			time[i][0]=s+a;    //单个学生答疑结束发送消息所需的时间
			time[i][1]=e;      //收拾东西的时间
		}
		Arrays.sort(time,1,n+1,new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if((o1[0]+o1[1])==(o2[0]+o2[1])) {
					return o1[0]-o2[0];
				}
				return (o1[0]+o1[1])-(o2[0]+o2[1]);
			}
		});
		int dp[]=new int[1005];
		long result=0;    //答案可能超过int所能表示的范围
		dp[1]=time[1][0];
		for(int i=2;i<=n;i++) {
			dp[i]=dp[i-1]+time[i-1][1]+time[i][0];
		}
		for(int i=1;i<=n;i++) {
			result+=dp[i];
		}
		pr.print(result);
		pr.flush();
	}
}

【总结】

        此题是较为经典的贪心算法，在熟练掌握的情况下没有什么难度。祝大伙不论在比赛还是在职场上都能顺风顺水，一路开挂。