机器人跳跃问题和毕业旅行-头条2019笔试题

机器人跳跃问题-头条2019笔试题

机器人正在玩一个古老的基于DOS的游戏。

游戏中有N+1座建筑——从0到N编号,从左到右排列。

编号为0的建筑高度为0个单位,编号为 i 的建筑高度为H(i)个单位。

起初,机器人在编号为0的建筑处。

每一步,它跳到下一个(右边)建筑。

假设机器人在第k个建筑,且它现在的能量值是E,下一步它将跳到第k+1个建筑。

如果H(k+1)>E,那么机器人就失去H(k+1)-E的能量值,否则它将得到E-H(k+1)的能量值。

游戏目标是到达第N个建筑,在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏,才可以保证成功完成游戏?

输入格式

第一行输入整数N。

第二行是N个空格分隔的整数,H(1),H(2),…,H(N)代表建筑物的高度。

输出格式

输出一个整数,表示所需的最少单位的初始能量值上取整后的结果。

数据范围

1≤N,H(i)≤(10^5)

输入样例1:

5
3 4 3 2 4

输出样例1:

4

输入样例2:

3
4 4 4

输出样例2:

4

输入样例3:

3
1 6 4

输出样例3:

3

暴力二分

注意的点:当前能量值大于剩余建筑的最大值时,则一定可以通过,如果按照递推公式算下去会超long的范围,一定要提前判断是否可以直接通过。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        double max = 0D;
        for(int i=0; i < n; i++) {
            a[i] = sc.nextInt();
            if(max < a[i] ) max = a[i];
        }
        long t = 0;
        int[] maxn = new int[n];
        for(int i=n-1; i >= 0; i--) {
            if(i == n-1)
                maxn[i] = a[i];
            else
                maxn[i] = Math.max(maxn[i+1], a[i]);
        }
        // System.out.println(max);
        double l = 0.0D, r = max;
        while(Math.abs(r-l) > 0.1) {
            double mid = (l+r)/2;
            boolean finished = true;
            long powers = (2*((long)mid)+ 1) / 2;
            for(int i=0; i < n; i++) {
                if(powers >= maxn[i]) break;
                if(powers > a[i]) 
                    powers += (powers - a[i]);
                else
                    powers -= (a[i] - powers);
                // System.out.println("i:"+i + "," + powers);
                if(powers < 0) {
                    finished = false;
                    break;
                }
            }
            // System.out.println(finished);
            if(finished) {
                r = mid;
            } else {
                l = mid;
            }
        }
        System.out.println(((2*(long)r) + 1) / 2);
    }
}

毕业旅行-头条2019笔试题

小明目前在做一份毕业旅行的规划。

打算从北京出发,分别去若干个城市,然后再回到北京,每个城市之间均乘坐高铁,且每个城市只去一次。

由于经费有限,希望能够通过合理的路线安排尽可能的省些路上的花销。

给定一组城市和每对城市之间的火车票的价钱,找到每个城市只访问一次并返回起点的最小车费花销。

注意:北京为1号城市。

输入格式

城市个数n

城市间的车票价钱n行n列的矩阵 m[n][n]

输出格式

输出一个整数,表示最小车费花销。

数据范围

1<n≤20,包括北京车票价格均不超过1000元。

输入样例:

4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

输出样例:

13

说明

共4个城市,城市1和城市1的车费为0,城市1和城市2之间的车费为2,城市1和城市3之间的车费为6,城市1和城市4之间的车费为5,以此类推。

假设任意两个城市之间均有单程票可买,且价格均在1000元以内,无需考虑极端情况。

状态压缩DP问题,直接暴力了。

import java.util.*;
public class Main {
    static List<Integer> res;
    static int[][] d;
    static int mind ;
    static boolean[] st;
    static void dfs(int n, int u) {
        if(n == u) {
            int dis = d[0][res.get(n-1)];
            for(int i=1; i < n; i++)
                dis += d[res.get(i-1)][res.get(i)];
            if(mind > dis) mind = dis;
            return;
        }
        for(int i=0; i < n; i++) {
            if(st[i] != true) {
                st[i] = true;
                res.add(i);
                dfs(n, u+1);
                res.remove(res.size() - 1);
                st[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        d = new int[n][n];
        st = new boolean[n];
        for(int i=0; i <  n; i++) {
            for(int j=0; j < n; j++)
                d[i][j] = sc.nextInt();
        }
        mind = Integer.MAX_VALUE;
        res = new ArrayList<>();
        res.add(0); st[0] = true;
        dfs(n, 1);
        System.out.println(mind);
    }
}
原文地址:https://www.cnblogs.com/lixyuan/p/12969434.html