接上篇博客，网易笔试第二题：买票问题。
游乐场中有n个人排队买票，早上8点开始卖票，每个人买票的方式有两种：
① 单独买，只买自己的票，每个人花费时间为a[i]秒
② 和后一个人一起买，一共花费时间为b[i]秒
最后一个人只能和前面的人一起买或者单独购买。
游乐场希望尽早下班，问游乐园最早下班时间为几点？
输入为T（有多少组案例）、n（有多少个人排队）、a（有n个数字，a[i]表示第i个人单独买花费的时间）、b（有n-1个数字，b[i]表示第i个人与前一个人一起买花费的时间）。
输出为：08:00:00 AM 、 10:36:42 PM 这种形式。
可以使用动态规划方法去做，dp[i]表示到第i个人花费的最少时间，到第i个人时，只可能由两种状态转移而来，第一种是前一个人的最优解，然后第i个人自己去买票，此时第i个人花费的最少时间dp[i]为dp[i - 1] + a[i]，还有一种是往前两个人的最优解，然后第i个人与第i-1个人一起去买票，此时第i个人花费的最少时间dp[i]为dp[i - 2] + b[i - 1]。所以对于第i个人来说，最优解即为这两种情况中的最优值，则转移方程为dp[i] = min(dp[i - 1] + a[i], dp[i - 2] + b[i - 1])。这里b[i - 1]是因为b为一个n-1维数组，这里也可以将数组b的最前边补一个0，这样的话就可以写作b[i]。
然后需要注意的地方为输出格式问题，还有就是要转化为12小时制，14点需要写成2点。
Talk is cheap, show me the code.
import java.util.Scanner;public class NETest2 {private static String helper(int seconds){int hours = seconds / 3600 + 8;String ap = hours > 12 ? "PM" : "AM";if (hours > 12){hours -= 12;}String h = hours > 9 ? hours + "" : "0" + hours ;seconds = seconds % 3600;int minutes = seconds / 60;String m = minutes > 9 ? minutes + "" : "0" + minutes ;seconds = seconds % 60;int second = seconds % 60;String s = second > 9 ? second + "" : "0" + second ;return h + ":" + m + ":" + s + " " + ap;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int batch = sc.nextInt();for (int i = 0; i < batch; i++) {int n = sc.nextInt();int[] a = new int[n];int[] b = new int[n - 1];for (int j = 0; j < n; j++) {a[j] = sc.nextInt();}for (int j = 0; j < n - 1; j++) {b[j] = sc.nextInt();}int[] dp = new int[n];dp[0] = a[0];dp[1] = Math.min(a[0]+a[1], b[0]);for (int j = 2; j < n; j++) {dp[j] = Math.min(dp[j - 1] + a[j], dp[j - 2] + b[j - 1]);}System.out.println(helper(dp[n - 1]));}}
}
多做复盘才能进步，共勉。