AtCoder Beginner Contest 325

Takahashi san

public static void solve() {
    String s = io.next();
    io.next();
    io.println(s + " san");
}

World Meeting

比赛时用滑窗没有做出来，原来要滑两倍的数组长度啊。

public static void solve() {
    int n = io.nextInt();
    int[] cnt = new int[24];
    for (int i = 0; i < n; i++) {
        int w = io.nextInt(), x = io.nextInt();
        cnt[x] += w;
    }

    int ans = 0;
    for (int i = 0; i < 24; i++) {
        int sum = 0;
        for (int j = 0; j < 9; j++) {
            sum += cnt[(i + j) % 24];
        }
        ans = Math.max(ans, sum);
    }
    io.println(ans);
}

Sensors

直接 DFS 或者并查集都行。

public static void solve() {
    int h = io.nextInt(), w = io.nextInt();
    boolean[][] g = new boolean[h][w];
    for (int i = 0; i < h; i++) {
        String s = io.next();
        for (int j = 0; j < w; j++) {
            if (s.charAt(j) == '#') {
                g[i][j] = true;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (g[i][j]) {
                ans++;
                dfs(i, j, g);
            }
        }
    }
    io.println(ans);
}

private static void dfs(int x, int y, boolean[][] g) {
    if (x < 0 || x >= g.length || y < 0 || y >= g[0].length || !g[x][y]) return;
    g[x][y] = false;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            dfs(x + i, y + j, g);
        }
    }
}

Printing Machine

贪心，对于每个时刻，我们选择已经进入传送带的，右端点最小的产品。

public static void solve() {
    int n = io.nextInt();
    long[][] aux = new long[n][];
    for (int i = 0; i < n; i++) {
        long t = io.nextLong(), d = io.nextLong();
        aux[i] = new long[]{t, t + d};
    }
    Arrays.sort(aux, (a, b) -> Long.compare(a[0], b[0]));

    int i = 0, ans = 0;
    Queue<Long> q = new PriorityQueue<>();
    for (long t = 0; ; t++) {
        if (q.isEmpty()) {
            if (i == n) break;
            t = aux[i][0];
        }
        while (i < n && aux[i][0] == t) {
            q.offer(aux[i++][1]);
        }
        while (!q.isEmpty() && q.peek() < t) {
            q.poll();
        }
        if (!q.isEmpty()) {
            ans++;
            q.poll();
        }
    }
    io.println(ans);
}