AtCoder Beginner Contest 331 题解 A-E

A - Tomorrow

原题链接

题目描述
已知一年有M个月D天，求出第y年m月d天的后一天是哪一天。

思路：分类讨论

分别讨论m和d的是否是最后一个月或者最后一天即可。

public static void solve() throws IOException {
    int n = readInt(), m = readInt();
    int a = readInt(), b = readInt(), c = readInt();
    if (c < m) {
        printWriter.println(a + " " + b + " " + (c + 1));
    } else {
        if (b == n) {
            printWriter.println((a + 1) + " "  + 1 + " " + 1);
        } else {
            printWriter.println(a + " " + (b + 1) + " " + 1);
        }
    }
}

B - Buy One Carton of Milk

原题链接

题目描述
一家超市正在销售鸡蛋。一包 $6$ 个鸡蛋售价 $S$ 日元，一包 $8$ 个鸡蛋售价 $M$ 日元，一包 $12$ 个鸡蛋售价 $L$ 日元。你可以购买任意数量的每包鸡蛋，求至少购买 $N$ 个鸡蛋所需的最小金额。

思路：枚举

分别枚举每包鸡蛋购买的数量，求出最小值。

public static void solve() throws IOException {
    int n = readInt();
    int a = readInt(), b = readInt(), c = readInt();
    int min = Integer.MAX_VALUE;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                if (i * 6 + j * 8 + k * 12 >= n) {
                    min = Math.min(min, i * a + b * j + c * k);
                }
            }
        }
    }
    printWriter.println(min);
}

C - Sum of Numbers Greater Than Me

原题链接

题目描述
给你一个长度为 $N$ 的序列 $A=(A_1,\ldots,A_N)$ 。对于每个 $i=1,\ldots,N$ ，求出 $A$ 中所有大于 $A_i$ 的元素之和。

思路：排序+前缀和+二分

对于每个 $A_i$ ，求出它在排序好的数组中，后面比它大的数的和即可，具体看代码注释。

public static void solve() throws IOException {
    int n = readInt();
    int[] arr = new int[n + 1];
    int[] arr2 = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        arr[i] = readInt();
        arr2[i] = arr[i];
    }
    Arrays.sort(arr2, 1, n + 1);
    long[] pre = new long[n + 1];
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + arr2[i];// 前缀和
    }
    for (int i = 1; i <= n; i++) {
        int l = 0, r = n + 1;
        // 二分找到 arr[i]在 arr2中最后一次出现的位置
        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (arr2[mid] <= arr[i]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        if (l == 0 || r == n + 1) {// arr[i]已经最大
            printWriter.print(0 + " ");
        } else {
            printWriter.print((pre[n] - pre[l]) + " ");
        }
    }
}

D - Tile Pattern

原题链接

题目描述
有一个无穷大的正方形网格。网格中的每个方格都是黑色或白色的。方格 $(i, j)$ 的颜色由字符 $\bmod N][j \bmod N]$ 表示，其中 B 表示黑色，W 表示白色。这里， $\bmod b$ 表示 $a$ 除以 $b$ 的余数。然后给出 $Q$ 个查询，每个查询给出四个整数 $A, B, C, D$ ，要求你找出以 $(A, B)$ 为左上角， $(C, D)$ 为右下角的矩形区域中包含的黑色方格的个数。

思路：前缀和

先根据已给出的 $\times n$ 的网格计算出前缀和。
然后可以根据 $A, B, C, D$ 将图形分为四个区域，且让四区域的左上角都为 $(0, 0)$ ，右下角分别为 $(A - 1, B - 1), (A - 1, D), (C, B - 1), (C, D)$ 。

分好区域后，又可以将每个区域分为四部分。假设一个区域有 $r$ 行 $c$ 列，那么 ①左上角有 $(r / n) * (c / n)$ 个 $n * n$ 大小的网格，②右上角有 $(r / n)$ 个 $\% n)$ 大小的网格，③左下角有 $(c / n)$ 个 $\% n) * n$ 大小的网格，④右下角有一个 $\% n) * (c \% n)$ 大小的网格。
最后再通过前缀和的方式得到 $(A, B)$ 为左上角， $(C, D)$ 为右下角的矩形区域中包含的黑色方格的个数。

static int n, q;
static long[][] pre;

public static void solve() throws IOException {
    n = readInt(); q = readInt();
    pre = new long[n + 1][n + 1];
    for (int i = 1; i <= n; i++) {
        String s = (" " + readString());
        for (int j = 1; j <= n; j++) {
            if (s.charAt(j) == 'B') pre[i][j] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
        }
    }

    while (q-- > 0) {
        int a = readInt() + 1, b = readInt() + 1;// 左上角
        int c = readInt() + 1, d = readInt() + 1;// 右下角
        printWriter.println(calc(c, d) - calc(c, b - 1) - calc(a - 1, d) + calc(a - 1, b - 1));
    }
}

public static long calc(int r, int c) {
    long sum = 0;
    sum += 1l * (r / n) * (c / n) * pre[n][n];// 左上
    sum += 1l * (r / n) * pre[n][c % n];// 右上
    sum += 1l * (c / n) * pre[r % n][n];// 左下
    sum += 1l * pre[r % n][c % n];// 右下
    return sum;
}

E - Set Meal

原题链接

题目描述
一家餐厅出售的饭菜包括一道主菜和一道配菜。主菜有 $N$ 种，主菜 $i$ 的价格为 $a_i$ 日元。配菜有 $M$ 种，配菜 $i$ 的价格为 $b_i$ 日元。套餐由一道主菜和一道配菜组成，价格为所选主菜和配菜价格的总和。
但是餐厅不提供 $L$ 对不同的由主菜 $c_i$ 和配菜 $d_i$ 组成的套餐。也就是说，餐厅只提供了 $N * M - L$ 份套餐。请你求出可以提供的最贵套餐的价格。

思路：排序+多路归并

将主菜和配菜降序排序，再构建一个大顶堆，实现多路归并。
先让每个主菜与第一个配菜组成套餐，即入队。
寻找答案：如果堆顶元素可以组成套餐，那么输出答案，否则让该主菜和下一个配菜组成套餐，入队。

public static void solve() throws IOException {
    int n = readInt(), m = readInt(), L = readInt();
    Pair[] a = new Pair[n], b = new Pair[m];
    for (int i = 0; i < n; i++) a[i] = new Pair(i, readInt());
    for (int i = 0; i < m; i++) b[i] = new Pair(i, readInt());
    Arrays.sort(a, (p, q) -> q.second - p.second);// 降序
    Arrays.sort(b, (p, q) -> q.second - p.second);
    Map<Integer, Set<Integer>> map = new HashMap<>();// 不提供的套餐
    for (int i = 0; i < L; i++) {
        int c = readInt() - 1, d = readInt() - 1;
        Set<Integer> set = map.getOrDefault(c, new HashSet<>());
        set.add(d);
        map.put(c, set);
    }
	// 大顶堆，按照 a[i] + b[j]降序排序
    PriorityQueue<int[]> deque = new PriorityQueue<>((p, q) -> {
        return a[q[0]].second + b[q[1]].second - (a[p[0]].second + b[p[1]].second);
    });
    for (int i = 0; i < n; i++) {
        deque.offer(new int[]{i, 0});
    }
    // 注意入队时，使用排序好的数组下标
    // 计算时，使用原数组的下标
    while (deque.size() > 0) {
        int[] t = deque.poll();
        if (!map.getOrDefault(a[t[0]].first, new HashSet<>()).contains(b[t[1]].first)) {
            printWriter.println(a[t[0]].second + b[t[1]].second);
            return;
        }
        if (t[1] + 1 < m) {// 下一个配菜
            deque.offer(new int[]{t[0], t[1] + 1});
        }
    }
}