2020校招途家名宿开发笔试

小家的守望者的逃离

题目描述

法师住在一个村庄，一天发生雪崩，法师跑步速度为 13m/s，使用魔法 1s 可以移动 50m，但会扣除 10 点魔法值
法师初始魔法值 M，村庄到安全地的距离为 S，雪崩到达的时间为 T，法师恢复魔法速度为 4点/s，但是只有原地不动才可以恢复

输入

输入一行，包括3个非负整数M，S，T

输出

输出两行
第一行输出"Yes","No"，表示是否到达安全地
第二行输出到达的时间或时未到达时达到的最大距离

样例输入

36 255 10

样例输出

Yes
10

思路

2种逃跑方式，跑步和使用魔法，直接贪心即可

1. 在魔法值充足的情况下，可以使用 M/10 次魔法进行逃跑
2. 计算可得，当剩余魔法值 >= 2 时，等待恢复使用一次魔法才会比直接跑步有优势
   注：当然你需要关注时间是否充足，以及你距离安全地的距离，你都剩下 13m 了就没必要等待使用一次魔法的时间了
3. 魔法值用完后，剩下时间当然直接跑了。。。

编码

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int m = scn.nextInt(), s = scn.nextInt(), t = scn.nextInt();
        // count：初始魔法值能用几次 tAns：记录使用的时间 sAns：记录走过的路程 flag：此处标记剩余魔法值是否为 4 的倍数
        int count = m/10, sAns = 0, tAns = 0, tt = 0, flag = (10-m%10)%10%4 == 0 ? 0 : 1;
        if(m%10 > 1 && m%10/4 + flag <= t) {                 // tt记录下恢复到至少 10 点魔法值所需时间
            tt = m%10 / 4 + flag;
        }
        flag = s%50 == 0 ? 0 : 1;                            // 此处标记路程是否为 50 的倍数
        count = Math.min(count, Math.min(s/50+flag,t));
        sAns += count * 50;
        tAns += count;
        if(tt != 0 && tt+1 <= t-tAns && tt*13 + sAns < s) {  // 存在多余魔法值 未被淹没 使用等待的时间直接走不会到达目的地
            sAns += 50;
            tAns += tt + 1;
        }
        flag = (s-sAns)%13 == 0 ? 0 : 1;                     // 此处标记剩余路程为 13 的倍数
        count = Math.min((s-sAns)/13+flag, (t-tAns));
        sAns += count * 13;
        tAns += count;
        if(sAns < s) {
            System.out.println("No");
            System.out.println(sAns);
        } else {
            System.out.println("Yes");
            System.out.println(tAns);
        }
    }
}

---

小家的旅行路线

题目描述

有 N 座城市，M 条路线，现马可波罗想要去其中 R 个城市，请帮他制定一个最短路线。
路线为无向边，保证无重边

输入

第一行输入 N，M，R（2 <= N <= 200，1 <= M <=500，2 <= R <= min(22,N)
第二行输入 R 个城市的编号
之后 M 行每行输入x，y，z 表示城市 x 和城市 y 之间相距 z 米（z <= 10000）

输出

路线的最短距离

样例输入

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

样例输出

3

思路

搜索遍历即可
起点一定是需要去的城市
返回的条件是所有需要去的城市都去过了
通过对比路径 与 ans（历史搜索出现的最短路径） 可以剪掉一些过长的路线

编码

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    private static int[][] map;                     // 邻接矩阵记录路线
    private static int[] vis;                       // 记录是否去过某城市
    private static Set<Integer> set;                // 记录是否去过需要去的城市
    private static int n, ans = Integer.MAX_VALUE;  // ans 记录最短路径
    private static int dfs(int x, int s) {
        if(s > ans) return Integer.MAX_VALUE;       // 超过之前的最优路径，没必要继续走
        if(set.isEmpty()) return s;                 // 需要去的城市都去过，即找到路线
        int tmp = Integer.MAX_VALUE;                // 记录到达 x 之后， 后面的最短路线
        for(int i = 1; i <= n; ++i) {
            if(map[x][i] > 0 && vis[i] == 0) {
                boolean flag = set.remove(i);
                vis[i] = 1;
                tmp = Math.min(dfs(i, s+map[x][i]), tmp);
                vis[i] = 0;
                if(flag) set.add(i);
            }
        }
        return tmp;
    }
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        n = scn.nextInt();
        int m = scn.nextInt(), r = scn.nextInt();
        map = new int[n+1][n+1];
        vis = new int[n+1];
        set = new HashSet<Integer>();
        for(int i = 0; i < r; ++i) {
            set.add(scn.nextInt());
        }
        for(int i = 0; i < m; ++i) {
            int x = scn.nextInt(), y = scn.nextInt(), z = scn.nextInt();
            map[x][y] = map[y][x] = z;
        }
        for(int i = 1; i < n; ++i) {
            if(set.contains(i)) {                   // 只有需要去的城市才作为起点进行搜索
                set.remove(i);
                vis[i] = 1;
                ans = Math.min(dfs(i, 0), ans);
                vis[i] = 0;
                set.add(i);
            }
        }
        System.out.println(ans);
    }
}