腾讯2020校招笔试题-小Q放假

偏执的太偏执、 2023-08-17 17:39 161阅读 0赞

#### 腾讯2020校招笔试题 ####

#### 题目 ####

> 公司给小Q放了n天的假,他有个奇怪的习惯:不会连续两天工作或段炼
> 
> 只有当公司开业,小Q才能去工作,
> 
> 只有当健身房营业时,小O才能去健身,
> 
> 小Q一天只能干一件事.给出假期中公司,健身房的营业情兄,求小Q最少需要体息几天
> 
> 输入描述第ー行一个数表示放假天数n
> 
> 第二行n个数字，数字为0或者1,第i个数表示公司在第1天是否营业
> 
> 第三行n个数字，数字为0或者1,第i个数表示健身房在第i天是否营业
> 
> （1为营业0为不营业)

#### example ####

#### 输入 ####

4
    1 1 0 0
    0 1 1 0

#### 输出 ####

2
    小Q可以在第一天工作，第二或者第三健身，最少休息两天

#### 思路 ####

典型的动态规划题目, 稍微注意一些条件

d p \[ 0 \] \[ i \] dp\[0\]\[i\] dp\[0\]\[i\],  d p \[ 1 \] \[ i \] dp\[1\]\[i\] dp\[1\]\[i\],  d p \[ 2 \] \[ i \] dp\[2\]\[i\] dp\[2\]\[i\]分别代表`第i天休息最少休息天数`、`第i天工作最少休息天数`、`第i天健身最少休息天数`

可以得到以下递推公式

$dp\[0\]\[i\] = min(dp\[0\]\[i-1\], dp\[1\]\[i-1\], dp\[2\]\[i-1\]) + 1 $

**注意只有第 i − 1 i-1 i−1 可以健身或者锻炼才把 d p \[ 1 \] \[ i − 1 \] dp\[1\]\[i-1\] dp\[1\]\[i−1\],  d p \[ 2 \] \[ i − 1 \] dp\[2\]\[i-1\] dp\[2\]\[i−1\]考虑进去,下同**

$dp\[1\]\[i\] = min(dp\[0\]\[i-1\],dp\[2\]\[i-1\]) $ **只有第i天可以工作，才有此式子**

$dp\[2\]\[i\] = min(dp\[0\]\[i-1\], dp\[1\]\[i-1\]) $ **只有第i天可以健身，才有此式子**

有了递推公式，码代码只是时间的问题

#### java AC代码 ####

import java.util.Scanner;
    import java.io.File;
    import java.lang.Math;
    public class Main{ 
        public static void main(String args[]) throws Exception{ 
            //File file = new File("in.txt");
            //Scanner sc = new Scanner(file);
            Scanner sc = new Scanner(System.in);
            int number = sc.nextInt();
            int []keep = new int[number+1];
            int []work = new int[number+1];
            for(int i = 1; i <= number; i++) work[i] = sc.nextInt();
            for(int i = 1; i <= number; i++) keep[i] = sc.nextInt();
    
            int [][] dp = new int[3][number+1];
    
            //第一天休息
            dp[0][1] = 1;
    
            //第一天工作
            if(work[1] == 1) dp[1][1] = 0;
            else dp[1][1] = number + 1;
    
            //第一天健身
            if(keep[1] == 1) dp[2][1] = 0;
            else dp[2][1] = number + 1;
    
            for(int i = 2; i <= number; i++) { 
                dp[0][i] = Math.min(Math.min(dp[1][i-1], dp[2][i-1]), dp[0][i-1]) + 1;
                if (work[i] == 1) { 
                    dp[1][i] = Math.min(dp[2][i-1], dp[0][i-1]);
                }else dp[1][i] = number + 1;
    
                if(keep[i] == 1) { 
                    dp[2][i] = Math.min(dp[1][i-1], dp[0][i-1]);
                }else dp[2][i] = number + 1;
            }
    
            System.out.println(Math.min(Math.min(dp[0][number], dp[1][number]), dp[2][number]));
            sc.close();
        }
    
    }