小美的仓库整理

2021-08-27

meituan-002. 小美的仓库整理

难度中等9收藏分享切换为英文接收动态反馈

小美是美团仓库的管理员，她会根据单据的要求按顺序取出仓库中的货物，每取出一件货物后会把剩余货物重新堆放，使得自己方便查找。已知货物入库的时候是按顺序堆放在一起的。如果小美取出其中一件货物，则会把货物所在的一堆物品以取出的货物为界分成两堆，这样可以保证货物局部的顺序不变。
已知货物最初是按 1~n 的顺序堆放的，每件货物的重量为 w[i] ,小美会根据单据依次不放回的取出货物。请问根据上述操作，小美每取出一件货物之后，重量和最大的一堆货物重量是多少？

格式：

输入：
- 输入第一行包含一个正整数 n ，表示货物的数量。
- 输入第二行包含 n 个正整数，表示 1~n 号货物的重量 w[i] 。
- 输入第三行有 n 个数，表示小美按顺序取出的货物的编号，也就是一个 1~n 的全排列。
输出：
- 输出包含 n 行，每行一个整数，表示每取出一件货物以后，对于重量和最大的一堆货物，其重量和为多少。

示例：

输入：
     5
     3 2 4 4 5 
     4 3 5 2 1
输出：
     9
     5
     5
     3
     0
解释：
原本的状态是 {{3,2,4,4,5}} ，取出 4 号货物后，得到 {{3,2,4},{5}} ，第一堆货物的和是 9 ，然后取出 3 号货物得到 {{3,2}{5}} ，此时第一堆和第二堆的和都是 5 ，以此类推。

提示：

1 <= n,m <= 50000
1 <= w[i] <= 100
请注意，本题需要自行编写「标准输入」和「标准输出」逻辑，以及自行 import/include 需要的 library。了解书写规则

反向操作(插入)

利用一个数据维护当前位置的元素所在区域的左边界和右边界，每次更新的同时更新左边界和右边界，这样就能实现边界的维护。

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] w = new int[n + 1];
        int[] poll = new int[n + 1];
        int[] preSum = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
            preSum[i] = preSum[i - 1] + w[i];
        }

        for (int i = 1; i <= n; i++) {
            poll[i] = sc.nextInt();
        }

        int[][] d = new int[n + 1][2];
        for (int i = 0; i <= n; i++) {
            d[i] = new int[] { -1, -1 };// 将d数组值初始化为-1,便于判断空位置
        }

        int[] res = new int[n+1];// 存储结果的数组

        int maxSum = 0;

        for (int i = n; i >= 0; i--) {
            int x = poll[i];
            res[i] = maxSum;
            if (i == 0) break;
            // 更新最大重量
            int cur = w[x];
            int left = x, right = x;// 左边界和右边界,注意如果左右无连通区域则区间为[x,x],所以初始化为x
            // 每次只会将左右两块区域连成一块,我们只需关心一段区间的左边界和右边界,就能通过前缀和数组查询到区间和
            if (x + 1 <= n && d[x + 1][0] != -1) {
                // 如果右边界不为空，计算右边这一块区域的和
                cur += preSum[d[x + 1][1]] - preSum[d[x + 1][0] - 1];
                right = d[x + 1][1]; // 更新右边界(原先右边的右边界)
            }
            if (x - 1 > 0 && d[x - 1][1] != -1) {
                // 如果左边界不为空,计算左边这一块区域的和
                cur += preSum[d[x - 1][1]] - preSum[d[x - 1][0] - 1];
                left = d[x - 1][0]; // 更新左边界(原先左边的左边界)
            }

            maxSum = Math.max(maxSum, cur);
            // 更新两端点的左右区间
            d[left][0] = left;
            d[left][1] = right;
            d[right][0] = left;
            d[right][1] = right;
        }
        for (int i = 1; i <= n; i++) {
            System.out.println(res[i]);
        }
    }

}

优先队列（超时）

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] w = new int[n + 1];
        int[] poll = new int[n + 1];

        int[] preSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
            preSum[i] = preSum[i - 1] + w[i];
        }

        for (int i = 1; i <= n; i++) {
            poll[i] = sc.nextInt();
        }

        PriorityQueue<Node> pq1 = new PriorityQueue<>((a, b) -> b.sum - a.sum);
        PriorityQueue<Node> pq2 = new PriorityQueue<>((a, b) -> b.sum - a.sum);
        PriorityQueue<Node> temp = null;
        pq1.offer(new Node(1, n, preSum[n]));

        for (int i = 1; i <= n; i++) {
            while (!pq1.isEmpty()) {
                Node node = pq1.poll();
                // 在当前的区间中
                int index = poll[i];
                if (index >= node.l && index <= node.r) {
                    // 左边剩余的值
                    int sum1 = preSum[index - 1] - preSum[node.l - 1];
                    // 右边的值
                    int sum2 = preSum[node.r] - preSum[index];

                    if (index - 1 >= node.l) {
                        Node node1 = new Node(node.l, index - 1, sum1);
                        pq2.offer(node1);
                    }
                    if (index + 1 <= node.r) {
                        Node node2 = new Node(index + 1, node.r, sum2);
                        pq2.offer(node2);
                    }
                } else {// 不在当前的区间中
                    pq2.offer(node);
                }
            }
            if (!pq2.isEmpty()) {
                System.out.println(pq2.peek().sum);
            } else {
                System.out.println(0);
            }

            temp = pq1;
            pq1 = pq2;
            pq2 = temp;
        }
    }

    static class Node {
        int l;
        int r;
        int sum;

        public Node(int l, int r, int sum) {
            this.l = l;
            this.r = r;
            this.sum = sum;
        }
    }
}