京东3.19笔试

坦克炸碉堡，用碉堡总血量算的，一开始没想过总血量会一次扣成负的，卡了好久。。。

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(), b = in.nextInt(), c = in.nextInt(), d = in.nextInt();
        long time = 0, total = d * b;
        while (d > 0) {
            if (a == 0)
                break;
            total -= a;
            if (total <= 0)
                d = 0;
            else
                d = (int) total / b + (total % b == 0 ? 0 : 1);
            a -= d * c;
            ++time;
        }
        System.out.println(d == 0 ? time : -1);
    }

第二题当无向图做了，暴力居然干过去了。。。

输入的时候记录一个max和min，二分的找第一个满足条件的重量

只要能从一个节点到达所有节点就算满足条件，所以每次都是从第一个节点开始找

private static boolean[] mem; //记录节点是否已被遍历

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = 4, m = 5;
        int min = 10000, max = 1;
        int[][] opt = new int[][] {
                {1, 2, 4}, {1, 3, 5}, {1, 4, 6}, {2, 3, 5}, {3, 4, 2}
        };
        Map<Integer, List<int[]>> map = new HashMap<>(); //key存储起点编号，int[]存储边
        int k = 0;
        while (k < m) {
                        //输入构建无向图
            int u = opt[k][0], v = opt[k][1], p = opt[k][2];
            min = Math.min(min, p);
            max = Math.max(max, p);
            List<int[]> list1 = map.get(u);
            if (list1 == null) {
                list1 = new ArrayList<>();
                map.put(u, list1);
            }
            list1.add(new int[] {v, p});
            List<int[]> list2 = map.get(v);
            if (list2 == null) {
                list2 = new ArrayList<>();
                map.put(v, list2);
            }
            list2.add(new int[] {u, p});
            ++k;
        }            
        while (min < max) {  //二分查找最大的重量target
            int mid = (min + max + 1) >> 1;
            mem = new boolean[n + 1];
                        mem[1] = true;
            if (check(map, 1, n, mid) == n) //若能到达节点数为n，则mid <= target
                min = mid;
            else
                max = mid - 1;
        }
        System.out.println(min);
    }

    private static int check(Map<Integer, List<int[]>> map,
                                 int idx, int n, int weight) {
        int k = 0; //记录能到达的节点数
        for (int[] edge : map.get(idx)) {
            if (mem[edge[0]] || weight > edge[1]) //节点已被遍历或超重
                continue;
            mem[edge[0]] = true;
            k += check(map, edge[0], n - 1, weight);
        }
        return k + 1; //要算上当前节点
    }

希望东哥能给个面