笔试真题系列-小美的仓库管理

默认文件1600262202579

大家好，这里是算法妙妙屋，今天为您带来一道美团真题

小美的仓库整理

题目描述

小美是美团仓库的管理员，她会根据单据的要求按顺序取出货物，每取出一件货物后会把剩余货物重新堆放，使得自己方便查找。已知货物入库的时候是按顺序堆放在一起的。如果小美取出其中一件货物，则会把货物所在的一堆物品以取出的货物为界限分为两堆，这样可以保证货物局部的顺序不变。

已知货物最初是按1-n的顺序堆放的，每件货物的重量为w_i，小美会根据单据依次不放回地取出货物。请问根据上述操作，小美每取出一件货物后，重量和最大的一堆货物重量是多少？

输入描述

输入第一行包含一个正整数n，表示货物的数量。（1<=n<=50000）

输入第二行包含n个正整数，表示1-n号货物的重量w_i。（1<=w_i<=100）

输入第三行有n个数，表示小美按顺序取出的货物的编号，也就是一个1-n的全排列。

输出描述

输出包括n行，每行一个整数，表示每取出一件货物以后，对于重量和最大的一堆货物，其重量和为多少。

样例输入

5
3 2 4 4 5
4 3 5 2 1

样例输出

9
5
5
3
0

题目分析

题目中说的是从一个长为 $n$ 的数组，按照一个 $1-n$ 的排列每次拿走一个元素，拿走的地方视为不连续，然后问你每次拿走后，剩下数组中的最大连续和是多少。

下面是样例的数据说明，我们用# 来代表被拿走的数字。

剩余元素	最大连续和	取走的元素
3 2 4 4 5	3 + 2 + 4 + 4 + 5 = 18	第4个
3 2 4 # 5	3 + 2 + 4 = 9	第3个
3 2 # # 5	3 + 2 = 5	第5个
3 2 # # #	3 + 2 = 5	第2个
3 # # # #	3 = 3	第1个
# # # # #	0 = 0	无

可以发现，从第二行第二列开始往下读，就是 9 5 5 3 0也就是我们的答案。

题意已经清楚了，下面就是求解了。

一种比较犀利的解法是将被挖去的地方视为负无穷，这样原来的问题就变成了单点更新，最大连续区间和的问题，但这种解法需要用到线段树，比较复杂。

线段树的知识我们以后有机会再介绍，针对这道题目，我们介绍一种思想上更巧妙的做法，同时时间复杂度上也是最优的，只需要 $O(n)$ 的时间。

这个思想就是将删除过程视为插入过程的逆过程，同时以一些方法维护插入过程的最大区间和。

剩余元素	最大连续和	添加的元素
# # # # #	0 = 0	无
3 # # # #	3 = 3	第1个
3 2 # # #	3 + 2 = 5	第2个
3 2 # # 5	3 + 2 = 5	第5个
3 2 4 # 5	3 + 2 + 4 = 9	第3个
3 2 4 4 5	3 + 2 + 4 + 4 + 5 = 18	第4个

可以看到，用插入的方式维护区间和非常合理，只不过得到的答案是逆序的，我们可以将所有输入一次性读入，用插入的方式处理后，再将答案逆序输出，这种方式被称为离线处理。

那么要如何在插入的过程中维护连续序列最大和呢？方法有很多，可以在这里找到。

这里采用的是那篇文章中的最后一种解法，在每个端点记录连续序列另一头的位置。与LeetCode128 不同的是，我们需要额外维护一个连续序列和，但求和这个东西很好维护，只需要 $O(1)$ 的时间就能维护了，所以总体时间复杂度也是 $O(n)$ 的。

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main()
{
    int n; cin >> n;

    vector<int> num(n);
    for (int i = 0; i < n; i++)
        cin >> num[i];

    vector<int> perm(n+1);
    for (int i = n; i >= 1; i--){
        cin >> perm[i];
        // 将排列从{1:n}转变到[0:n-1]
        perm[i]--;
    }
    // 记录连续区间的另一头
    unordered_map<int, int> mark;
    // 记录连续区间的和
    unordered_map<int, int> sum;

    vector<int> ans(n+1);
    ans[0] = 0;
    for (int i = 1; i <= n; i++){
            int v = perm[i];
            // 刚插入的时候，v的左右边界都是他本身，直接赋值即可
            mark[v] = v;
            // 刚插入的时候，v所在的连续序列和就是他本身
            sum[v] = num[v];
            // 若v是一个独立序列，更新答案
            ans[i] = max(ans[i-1], sum[v]);
            // 遍历左右，看是否存在已经插入的邻居
            for (auto u: {v-1, v+1}){
                auto it = mark.find(u);
                // 如果i+1的邻居已经存在于表中
                if (it != mark.end()){
                    // 用x代表v的另一端位置
                    // 用y代表v+i的另一端位置
                    int x = mark[v], y = mark[u];
                    // 两个端点分别记录位置
                    mark[x] = y;
                    mark[y] = x;
                    // 维护sum数组
                    // 由于是求sum 直接求和即可
                    sum[x] = sum[y] = sum[x] + sum[y];
                    // 维护答案
                    ans[i] = max(ans[i-1], sum[x]);
                }
            }
    }

    // 逆序输出答案
    for (int i = n-1; i >= 0; i--)
        cout << ans[i] << endl;

    // for_each(ans.rbegin()+1, ans.rend(), [](int& n){cout << n << endl;});

    return 0;
}