拼多多8.11后端笔试 个人解法分享

1. ac 看着描述复杂，实际访问顺序已经被题目定死了，按输入指定的优先级排序即可，纯模拟。整体复杂度O(n*log(n))

细节：景点第几天访问可以在O(1)时间内算出来，公式：((当前日期 - 最早日期）/ 每次延期天数)向下取整后 + 1) * 每次延期天数 + 最早日期

2. ac 优先队列，最短剩余时间优先，剩余时间相同最早布置优先。整体复杂度O(n*log(n))

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] task = new int[n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                task[i][j] = in.nextInt();
            }
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]));
        long ans = 0, cur = 0;  // cur表示当前时间
        for (int i = 0; i < n - 1; i++) {
            cur = task[i][0];
            pq.offer(task[i]);
            int interval = task[i + 1][0] - task[i][0];  // 距离下一项作业被布置的时间
            while (interval > 0 && !pq.isEmpty()) {
                int[] t = pq.peek();
                if (interval >= t[1]) {
                    pq.poll();
                    cur += t[1];
                    ans += (cur - t[0]);
                    interval -= t[1];
                } else {
                    t[1] -= interval;
                    interval = 0;
                }
            }
        }
        cur = task[n - 1][0];
        pq.offer(task[n - 1]);
        while (!pq.isEmpty()) {
            int[] t = pq.poll();
            cur += t[1];
            ans += (cur - t[0]);
        }
        System.out.println(ans);
    }

3. ac 核心的两点：

① 观赏度的奇偶性永远不变，要么永远奇数，要么永远偶数

② 假设观赏度能取负数(不取绝对值)，有这样一个结论：如果能取到的最大观赏度为mx，最小观赏度为mn，那么mx和mn之间的每个观赏度都能取到。严谨证明我没想过，但是从我ac了来看这个结论没问题

于是，题目转化为求最大观赏度和最小观赏度。然后就完全变成了“最大子数组和”问题。整体复杂度O(n)

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int curMaxSum = 0, curMinSum = 0;
        int maxSum = 0, minSum = 0;
        int totalSum = 0;
        for (int i = 0; i < n; i++) {
            int a = (in.nextInt() == 1 ? 1 : -1);
            totalSum += a;
            curMinSum = Math.min(curMinSum + a, a);
            minSum = Math.min(minSum, curMinSum);
            curMaxSum = Math.max(curMaxSum + a, a);
            maxSum = Math.max(maxSum, curMaxSum);
        }
        int minScore = totalSum - 2 * maxSum;
        int maxScore = totalSum - 2 * minSum;
        int ans = 0;
        if ((long) maxScore * minScore <= 0) {  // 最大最小观赏度是否同侧 分类讨论
            ans = Math.max(Math.abs(maxScore), Math.abs(minScore)) / 2 + 1;
        } else {
            ans = Math.abs(maxScore - minScore) / 2 + 1;
        }
        System.out.println(ans);
    }

4. 72%tle 转化为有向图。对于每个位置，从“线性探测时跨越的位置”到“最终位置”各连一条有向边。然后拓扑排序，排序顺序就是答案。对于字典序问题，把拓扑排序中的队列换成优先队列就行了。

但这样做最坏情况整体复杂度会达到O(n^2)，所以tle了，希望ac的朋友们分享下解法