Atcoder-ABC376

C. 题目链接

思路：对a和b排序，然后二分答案。check函数主要逻辑是将mid放在哪个位置更好，以及能不能把所有球给装完。

算法标签：二分答案、贪心。

时间复杂度：O(NLogN)

static boolean check(long mid, long[] a, long[] b) {
        int n = a.length;
        int i = 0, j = 0;
        boolean vis = false;
        for (i = 0; i < n; i++) {
            if (j == n - 1) {
                // 如果mid用过，或者a后面还有很多数字，或者mid < a[i]那么为false
                if (vis || i < n - 1 || mid < a[i]) return false;
                vis = true;
                continue;
            }
            if (a[i] > b[j]) {
                return false;
            }
            // 使用mid
            if (!vis && mid >= a[i] && mid <= b[j]) {
                vis = true;
                continue;
            }
            j++;
        }
        return i == n;
    }

    public static void solve() throws IOException {
        int n = in.nextInt();
        long[] a = new long[n];
        long[] b = new long[n-1];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextLong();
        }
        for (int i = 0; i < n - 1; i++) {
            b[i] = in.nextLong();
        }
        Arrays.sort(a);
        Arrays.sort(b);
        long l = 1;
        long r = (long) 2e14;
        while (l < r) {
            long mid = l + r >> 1;
            if (check(mid, a, b)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (!check(l, a, b)) {
            out.println(-1);
            return;
        }
        out.println(l);
    }

    static boolean MULTI_CASE = false;

    public static void main(String[] args) throws Exception {
        int T = MULTI_CASE ? in.nextInt() : 1;
        while (T-- > 0) {
            solve();
        }
        out.close();
    }

D. 题目链接

思路：题目是在有向图无权图求一个包含顶点1的最小的环。将两个点之间的权值看作1，然后一个包含顶点1的最小环其实可以变成一个最短路问题，假设u→v，这个v是1，我们可以把这个v看作0，题目就变成了求1到0的最短路，直接套dijkstra就行了。

算法标签：图论、最短路。

时间复杂度：O(NLogN)

public static void solve() throws IOException {
        int n = in.nextInt();
        int m = in.nextInt();
        List<int[]>[] g = new List[n + 10];
        Arrays.setAll(g, v -> new ArrayList<>());
        for (int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            if (v == 1) {
                v = 0;
            }
            g[u].add(new int[]{v, 1});
        }
        int[] dist = new int[n + 1];
        dijkstra0(1, 0, g, dist);
        out.println(dist[0] == Integer.MAX_VALUE ? -1 : dist[0]);
    }

    static void dijkstra0(int start, int end, List<int[]>[] g, int[] dist) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
        boolean[] vis = new boolean[g.length];
        pq.offer(new int[]{start, 0});
        dist[start] = 0;
        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            int u = p[0];
            if (u == end) return;
            if (vis[u]) continue;
            vis[u] = true;
            for (int[] next : g[u]) {
                int v = next[0], w = next[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }
    }