京东3.19后端笔试题

代码是可以优化的，随手写的提交比较快看看思路就好细节可以优化完成。

第一题贪心模拟即可

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(); //坦克
        int b = in.nextInt(); //碉堡血量
        int c = in.nextInt(); //一个碉堡炸c
        int d = in.nextInt(); //碉堡数量
        int cur = b; //初始化血量最少的碉堡血量为cur,刚开始为b
        int count = 0; 
        while (a != 0 && d != 0) { //如果坦克或碉堡任意为0结束
            count++;
            int tank = a; //坦克的攻击力总点数
            if (tank < cur) {
                cur -= tank; //未能消灭碉堡
            } else {
                while (tank >= cur && d != 0) {
                    d--;
                    tank -= cur;
                    cur = b;
                }
                if (d == 0) break; //碉堡全灭直接结束
                cur -= tank;
            }
            if (a - d * c > 0) {
                a = a - d * c; // 坦克未被全灭
            } else {
                a = 0; // 坦克被全灭（包括负数情形都设置为0）
                break;
            }
        }
        if (a == 0 && d != 0) {
            System.out.println(-1);
        } else {
            System.out.println(count);
        }
    }
}

第二题维护一个最大堆，从任意节点开始遍历，每次取最大value边出来，然后再加入连通的边且下一个点未访问过（保证一个最大所以不走回头路）

import java.util.*;

class edge {
    int dst, value;
}

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        List<List<edge>> edges = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            edges.add(new LinkedList<>());
        }
        int u, v, p;
        for (int i = 0; i < m; i++) {
            u = in.nextInt();
            v = in.nextInt();
            p = in.nextInt();
            edge e = new edge();
            e.dst = v;
            e.value = p;
            edges.get(u).add(e);
            edge e1 = new edge();
            e1.dst = u;
            e1.value = p;
            edges.get(v).add(e1); //可以给edge类加上带参构造方法把这一段变成2行时间关系不写了
        }
        Set<Integer> set = new HashSet<>();
        PriorityQueue<edge> pq = new PriorityQueue<>(new Comparator<edge>() { @Override public int compare(edge o1, edge o2) {
                return o2.value - o1.value;
            }
        }); //存放边的大根堆
        set.add(1); //随便选一个点进入set
        pq.addAll(edges.get(1)); //将该点所有连通边加入大根堆
        int max = Integer.MAX_VALUE; //用来维护路径上经过的最大的最小边权
        while (!pq.isEmpty()) {
            edge e = pq.poll();
            max = Math.min(max, e.value);
            set.add(e.dst);
            for (edge edge : edges.get(e.dst)) {
                if (!set.contains(edge.dst)) {
                    pq.add(edge);
                }
            }
            if (set.size() == n) {
                break;
            }
        }
        System.out.println(max);
    }
}

#京东暑期实习##笔经##京东##后端开发#