欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

网易面试笔试题(游乐场买票)

程序员文章站 2022-03-26 16:37:47
接上篇博客,网易笔试第二题:买票问题。游乐场中有n个人排队买票,早上8点开始卖票,每个人买票的方式有两种:① 单独买,只买自己的票,每个人花费时间为a[i]秒② 和后一个人一起买,一共花费时间为b[i]秒最后一个人只能和前面的人一起买或者单独购买。游乐场希望尽早下班,问游乐园最早下班时间为几点?输入为T(有多少组案例)、n(有多少个人排队)、a(有n个数字,a[i]表示第i个人单独买花费的时间)、b(有n-1个数字,b[i]表示第i个人与前一个人一起买花费的时间)。输出为:08:...

第一题地址:网易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