网易面试笔试题(游乐场买票)
第一题地址:网易2020/8/8笔试题(一)
第三题地址:网易2020/8/8笔试题(三)
接上篇博客,网易笔试第二题:买票问题。
游乐场中有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]));
}
}
}
多做复盘才能进步,共勉。
本文地址:https://blog.csdn.net/DebugMyself/article/details/107894768
上一篇: 简单选择排序