讨论/《美团 2021 届秋季校园招聘笔试真题》 - 小美的仓库整理/
《美团 2021 届秋季校园招聘笔试真题》 - 小美的仓库整理
共 16 个回复

从后向前逆序地放回货物,并且每次更新最大的一堆货物重量。如果放回的货物两侧还没有放货物,则只需要看这个货物的重量是否是最大。如果放回的货物两侧已经放了货物,需要把货物重量加到左侧或者右侧这一堆里去,可以借助并查集来实现货物重量的合并。

#include <bits/stdc++.h>

using namespace std;

vector<int> fa, sz;

int res = 0;

int find(int x){
    return x == fa[x] ? x : find(fa[x]);
}

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)
        return;
    fa[y] = x;
    sz[x] += sz[y];         // 合并货物重量
    res = max(res, sz[x]);  // 更新最大重量
}

int main(int argc, char* argv[]){

//    freopen("../input.txt", "r", stdin);

    int n;
    cin >> n;
    vector<int> nums(n);

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

    fa.resize(n);
    sz.resize(n);
    for(int i = 0; i < n; ++i){
        fa[i] = i;
        sz[i] = nums[i];  
    }

    vector<int> indexes(n);
    for(int i = 0; i < n; ++i){
        cin >> indexes[i];
        --indexes[i];
    }
    vector<bool> tmp(n, false);
    vector<int> vec(n);
    for(int i = n-1; i >= 0; --i){
        vec[i] = res;
        int j = indexes[i];
        res = max(res, nums[j]);      // 更新最大重量
        if(j + 1 < n && tmp[j + 1]){  
            unite(j, j + 1);          //将右侧货物重量合并到当前放的这个货物上
        }
        if(j > 0 && tmp[j - 1]){    
            unite(j - 1, j);          //将当前货物重量合并到左侧货物上
        }
        tmp[j] = true;
    }

    for(int x : vec)
        cout << x << endl;

    return 0;
}
4

用set来记录被拿走的货物的下标,并用pair记录当前重量最大的区间,每次首先判断取出的货物是否在pair区间内,如果不是直接利用前缀和输出最大,如果在区间内,说明区间被拆分,遍历set取得最大区间,因为区间的个数从1增长到n,所以复杂度是0(nlogn)。

#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);

    for (int i = 0; i < n; i++)
    {
        cin >> v[i];

    }


    vector<int> presum(n + 1);
    for (int i = 1; i <= n; i++)
    {
        presum[i] = presum[i - 1] + v[i - 1];
    }


    set<int> s;
    pair<int, int> pp = make_pair(0, n + 1);
    for (int i = 0; i < n; i++)
    {
        int idx;
        cin >> idx;
        s.insert(idx - 1);
        if (idx-1 >= pp.first && idx-1 < pp.second)
        {
            int now = 0;
            int maxsum = 0;
            for (auto& a : s)
            {
                if (maxsum < presum[a] - presum[now])
                {
                    maxsum = presum[a] - presum[now];
                    pp.first = now;
                    pp.second = a;

                    
                }
                now = a + 1;
            }
            if (maxsum < presum[n] - presum[now])
            {
                maxsum = presum[n] - presum[now];
                pp.first = now;
                pp.second = n;
            }
            cout << maxsum << endl;
        }
        else
        {
            cout << presum[pp.second] - presum[pp.first] << endl;
        }


    }
    return 0;


}
4

可以通过这个测试用例简单说明下:
3 2 4 4 5
4 3 5 2 1
我们逆序地放回货物,在这个过程中每一次放回都试图更新下最大值 res
一开始是这样子:
0 0 0 0 0
最大值 res = 0
放回倒数第一个拿走的货物:
3 0 0 0 0
先把放回的货物与最大值比较 res = max(res, 3) = 3
然后看一看放回的这个货物左右是否存在货物,没有,res为3,接着放下一个
放回倒数第二个拿走的货物:
3 2 0 0 0
先把放回的货物与最大值比较 res = max(res, 2) = 3
然后看一看放回的这个货物左右是否存在货物,先看右边,没有,再看左边,有一个重量为3的货物
这时候需要将这两堆货物进行合并变成一堆,也就是进行一次并查集的并操作。那怎么维护区间货物的重量呢?
用一个sz数组来维护,一开始sz=[3,2,4,4,5],每次并操作规定右边货物与左边货物进行合并

void unite(int x, int y){
    x = find(x);  //左边的货物找到区间最左
    y = find(y);  
    if(x == y)
        return;
    fa[y] = x;
    sz[x] += sz[y]; //更新合并后的区间货物重量
    res = max(res, sz[x]); //更新下这轮并操作之后的区间最大值
}

将重量为2的货物与重量为3的货物进行合并,更新sz[0]+=sz[1],[3,2]这个区间的重量更新了就是sz[0] = 5,
同时更新 res = max(res, sz[0]) = 5

放回倒数第三个拿走的货物:
3 2 0 0 5
先把放回的货物与最大值比较 res = max(res, 5) = 5
然后看一看放回的这个货物左右是否存在货物,先看右边,没有,再看左边,没有,接着放货物
放回倒数第四个拿走的货物:
3 2 4 0 5
先把放回的货物与最大值比较 res = max(res, 4) = 5
然后看一看放回的这个货物左右是否存在货物,先看右边,没有,再看左边,有一个重量为2的货物
这时候需要将这两堆货物进行合并变成一堆,注意这里重量为2的货物已经与重量为3的货物合并了,实际更新区间货物重量时都要通过并查集的查操作找到父节点,合并之后更新sz[0]+=sz[2],这样[3,2,4]这个区间的重量更新了,同时更新 res = max(res, sz[0]) = 9(每次并查集并操作后需要更新一次区间最大值)
最后一次放回,货物区间就满了,其实也没必要更新了。所以依次放回得到区间货物重量最大值为[0,3,5,5,9]
个人思路仅供参考,如有不对还请指正!

2
#include <iostream>
#include <vector>

using namespace std;

const int N = 50010;

int n, sum;
int w[N], idx[N];
int p[N], cnt[N];
bool st[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void unite(int a, int b) {
    a = find(a), b = find(b);
    p[a] = b;
    cnt[b] += cnt[a];
    sum = max(sum, cnt[b]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n; i++) {
        cin >> idx[i];
        p[i] = i;
    }

    vector<int> res;
    res.push_back(0);

    for (int i = n; i >= 2; i--) {
        int x = idx[i];

        st[x] = true;
        cnt[x] = w[x];
        sum = max(sum, cnt[x]);

        if (st[x - 1]) unite(x - 1, x);
        if (st[x + 1]) unite(x + 1, x);

        res.push_back(sum);
    }

    for (int i = n - 1; i >= 0; i--) cout << res[i] << endl;

    return 0;
}
import java.io.*;
import java.util.*;

class Solution {
    static final int N = 50010;

    static int n, sum;
    static int[] w = new int[N], idx = new int[N];
    static int[] p = new int[N], cnt = new int[N];
    static boolean[] st = new boolean[N];

    private static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    private static void unite(int a, int b) {
        a = find(a);
        b = find(b);
        p[a] = b;
        cnt[b] += cnt[a];
        sum = Math.max(sum, cnt[b]);
    }

    public static void main(String[] args) throws IOException {
        var reader = new BufferedReader(new InputStreamReader(System.in));
        var writer = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(reader.readLine());

        var strings = reader.readLine().split(" ");
        for (int i = 1; i <= n; i++) w[i] = Integer.parseInt(strings[i - 1]);

        strings = reader.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            idx[i] = Integer.parseInt(strings[i - 1]);
            p[i] = i;
        }

        List<Integer> res = new ArrayList<>();
        res.add(0);

        for (int i = n; i >= 2; i--) {
            int x = idx[i];

            st[x] = true;
            cnt[x] = w[x];
            sum = Math.max(sum, cnt[x]);

            if (st[x - 1]) unite(x - 1, x);
            if (st[x + 1]) unite(x + 1, x);

            res.add(sum);
        }

        for (int i = n - 1; i >= 0; i--) writer.write(res.get(i) + "\n");

        writer.flush();
        reader.close();
        writer.close();
    }
}
1
#include<iostream>
#include<vector>
using namespace std;

void unitLeftNeighbor(vector<int>& cur_heap_weight,vector<bool>& has_box,int cur_idx){
    int cur_weight = cur_heap_weight[cur_idx] + cur_heap_weight[cur_idx - 1];
    while (cur_idx >= 0 && has_box[cur_idx]){
        cur_heap_weight[cur_idx] = cur_weight;
        cur_idx --;
    }
}

void unitRightNeighbor(vector<int>& cur_heap_weight,vector<bool>& has_box,int cur_idx){
    int cur_weight = cur_heap_weight[cur_idx] + cur_heap_weight[cur_idx + 1];
    while (cur_idx < has_box.size() && has_box[cur_idx]){
        cur_heap_weight[cur_idx] = cur_weight;
        cur_idx ++;
    }
}

int main(){
    int size = 0;
    cin >> size;
    vector<int> weight(size);
    vector<int> index(size);
    for (int i = 0; i < size; i ++){
        cin >> weight[i];
    }
    for (int i = 0; i < size; i ++){
        cin >> index[i];
        index[i] --;
    }

    vector<bool> has_box(size,false);
    vector<int> cur_heap_weight(size,0);
    vector<int> ans (size,0);

    int max_weight = 0;
    ans[size - 1] = 0;
    for (int i = size - 1; i >= 1; i --){
        int idx = index[i];
        has_box[idx] = true;
        cur_heap_weight[idx] = weight[idx];

        //左邻居有堆放箱子
        if (idx > 0 && has_box[idx - 1])
        {
            unitLeftNeighbor(cur_heap_weight,has_box,idx);
        }
        
        //右邻居有堆放箱子
        if (idx < size - 1 && has_box[idx + 1]){
            unitRightNeighbor(cur_heap_weight,has_box,idx);
        }
        
        max_weight = max(max_weight,cur_heap_weight[idx]);
        ans [i - 1] = max_weight;
    }

    for (int i = 0; i < size; i ++){
        cout << ans[i] << endl;
    }

    
    return 0;
}

//解答错误 有大神指导一下吗 谢谢!
import java.util.Scanner;

public class Solution {
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int count = in.nextInt();
int[] height = new int[count];
for (int i=0; i<count; i++)//记录货物的重量,i表示第i件货物
{
height[i] = in.nextInt();
}
for (int i=0; i<count; i++)//开始取出,i表示第i次拿
{
int ch = in.nextInt();//拿走第ch件后,第ch件的重量为0
int sum1 = 0,sum2 = 0;
height[ch-1]=0;
for (int j=0; j<ch; j++)
{
sum1= sum1 + height[j];
}
for (int j=ch; j<count; j++)
{
sum2= sum2 + height[j];
}
if (sum1>sum2)
System.out.println(sum1);
else
System.out.println(sum2);
}
}
}

类似线段树的构造。

import sys
from itertools import accumulate
from typing import List

readline = sys.stdin.readline


def readint():
    return int(readline().strip())


def readstr():
    return readline().strip()


def readints():
    return list(map(int, readline().strip().split()))


class Node:
    def __init__(self, start: int, end: int, max: int):
        self.start, self.end, self.max = start, end, max
        self.left, self.right = None, None


def update(root: Node, k: int, presum: List[int]) -> None:
    if root.start < k < root.end and not root.left and not root.right:
        # left: [root->start+1,k-1], right: [k+1,root->end-1]
        leftsum = (k - 1 >= 0 and presum[k - 1]) - (
            root.start >= 0 and presum[root.start]
        )
        rightsum = (root.end >= 0 and presum[root.end - 1]) - (
            k >= 0 and presum[k]
        )
        root.left = Node(root.start, k, leftsum)
        root.right = Node(k, root.end, rightsum)
    elif root.left and k < root.left.end:
        update(root.left, k, presum)
    else:
        update(root.right, k, presum)
    root.max = max(root.left.max, root.right.max)


n = readint()
presum = list(accumulate(readints()))
s = readints()
root = Node(-1, n, presum[n - 1])
for k in s:
    update(root, k - 1, presum)
    print(root.max)
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int start, end, max;
    Node *left, *right;
    Node(int start, int end, int max)
        : start(start), end(end), max(max), left(nullptr), right(nullptr){};
};
void update(Node *root, int k, vector<int> &presum) {
    if (root->start < k && k < root->end && !root->left && !root->right) {
        // left: [root->start+1,k-1], right: [k+1,root->end-1]
        int leftsum = (k - 1 >= 0 ? presum[k - 1] : 0) -
                      (root->start >= 0 ? presum[root->start] : 0);
        int rightsum = (root->end - 1 >= 0 ? presum[root->end - 1] : 0) -
                       (k >= 0 ? presum[k] : 0);
        root->left = new Node(root->start, k, leftsum);
        root->right = new Node(k, root->end, rightsum);
    } else if (root->left && k < root->left->end) {
        update(root->left, k, presum);
    } else {
        update(root->right, k, presum);
    }
    root->max = max(root->left->max, root->right->max);
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n, w, k, sum = 0;
    cin >> n;
    vector<int> presum(n);
    for (int i = 0; i < n; ++i) {
        cin >> w;
        sum += w;
        presum[i] = sum;
    }
    Node *root = new Node(-1, n, presum[n - 1]);
    for (int i = 0; i < n; ++i) {
        cin >> k;
        update(root, k - 1, presum);
        cout << root->max << '\n';
    }
    return 0;
}

虽然通过了本题,但是实际上最差时间复杂度是 O(n2)\mathcal{O}(n^2),比如说

50000
1 2 ... 50000
1 2 ... 50000

这组数据就会超时。

大佬,执行出错哎,找不到自定义类,但是在本地环境就能跑出来,求教

tql,怎么想到的啊?逆序思考可以理解,但是如何维护区间和的较大值,想不明白

这段代码在牛客上能ac的 但是再leetcode上无法识别自己自定义的一个TreeNode类,编译不通过,有大佬知道该怎么引用自定义类嘛

import java.util.*;
import java.lang.*;

class TreeNode{
        int l;
        int r;
        int mid = -1;
        TreeNode left = null,right = null;
        public TreeNode(int l,int r){
            this.l = l;
            this.r = r;
        }
}

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[] sum = new int[n+1];
        for(int i = 1;i <= n;i++){
            w[i] = sc.nextInt();
            sum[i] = sum[i-1] + w[i];
        }

        Solution.TreeNode root = new Solution.TreeNode(1,n);
        
        Map<Integer,Integer> mp = new HashMap<>();
        mp.put(sum[n],1);
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.add(sum[n]);
    
        for(int k = 1;k <= n;k++){
            int idx = sc.nextInt();
           
           TreeNode node = root;
           while(node.mid != -1){
               if(node.mid > idx){
                   node = node.left;
               }else if(node.mid < idx){
                   node = node.right;
               }
           }
        
            
           int oldVal = sum[node.r] - sum[node.l-1];
            
           Integer count1 = mp.get(oldVal);
           if(count1 == 1){
               mp.remove(oldVal);
           }else{
               mp.put(oldVal,count1-1);
           }
            
           int val1 = 0,val2 = 0;
           if(node.r == idx){
               node.r = idx - 1;
               val1 = oldVal - w[idx];
               if(!mp.containsKey(val1)){
                   pq.add(val1);
               }
               mp.put(val1,mp.getOrDefault(val1,0)+1);
               
           }else if(node.l == idx){
               node.l = idx + 1;
               val2 = oldVal - w[idx];
               
               if(!mp.containsKey(val2)){
                   pq.add(val2);
               }
               mp.put(val2,mp.getOrDefault(val2,0)+1);
              
           }else{
               val1 = sum[idx-1] - sum[node.l-1];
               val2 = sum[node.r] - sum[idx];
               node.mid = idx;

               node.left = new TreeNode(node.l,idx-1);
               node.right = new TreeNode(idx+1,node.r);
               
               if(!mp.containsKey(val1)){
                   pq.add(val1);
               }
               
               if(!mp.containsKey(val2)){
                   pq.add(val2);
               }
               mp.put(val1,mp.getOrDefault(val1,0)+1);
               mp.put(val2,mp.getOrDefault(val2,0)+1);
               
           }
          
            while(!pq.isEmpty()){
                if(!mp.containsKey(pq.peek())){
                    pq.poll();
                }else{
                    break;
                }
            }
            
            System.out.println(pq.isEmpty()?0:pq.peek());
        }
    }
}