首页 > 试题广场 >

小美的仓库整理

[编程题]小美的仓库整理

热度指数：1979 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

输入描述:

输入第一行包含一个正整数n，表示货物的数量。(1<=n,m<=50000)
输入第二行包含n个正整数，表示1~n号货物的重量w_i。(1<=w_i<=100)
输入第三行有n个数，表示小美按顺序取出的货物的编号，也就是一个1~n的全排列。

输出描述:

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

示例1

输入

5
3 2 4 4 5 
4 3 5 2 1

输出

说明

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

算法知识视频讲解

我才不是游客

初始区间[1,n]，拿出元素i，区间为[1,i-1],[i+1,n]。随着每次选择元素拿出，区间数量都会增加。

如何根据位置X快速找到需要分割的区间，这个可以用set来维护。

每次我们可以通过位置X，在set中找到右端点大于等于x的第一个区间，这个就是我们需要分割的区间。删除区间并插入两个分割区间。

第二点，如何找到区间和的最大值，同样的思路用一个multiset维护。当我们找到待分割区间后，根据区间和，在multiset中找到这个值，删除插入两个区间和。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node
{
    int l,r;
    bool operator<(const node Y)const
    {
        return r<Y.r;
    }
};
set<node>st;
multiset<int>s;
int n,a[50005],sum[50005];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,x;
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>a[i],sum[i]=sum[i-1]+a[i];
    st.insert({1,n});
    s.insert(sum[n]);
    s.insert(0);
    for(i=1; i<=n; i++)
    {
        cin>>x;
        node t=*(st.lower_bound({x,x}));
        int l=t.l,r=t.r;
        st.erase(t);
        if(l<x)
            st.insert({l,x-1});
        if(r>x)
            st.insert({x+1,r});
        multiset<int>::iterator it=s.lower_bound(sum[r]-sum[l-1]);
        s.erase(it);
        if(l<x)
            s.insert(sum[x-1]-sum[l-1]);
        if(r>x)
            s.insert(sum[r]-sum[x]);
        it=s.end();
        it--;
        cout<<*(it)<<endl;
    }
    return 0;
}

发表于 2021-03-04 20:43:30 回复(2)

JCoder

将区间拆分逆序处理就变成了区间合并

说到合并当然就是并查集

多开两个数组 sum 和 ans，分别存放区间和以及每次操作的答案

#include <bits/stdc++.h>
using namespace std;

int n, a[50005], b[50005];
int fa[50005], sum[50005], ans[50005];
int maxx;
int find_fa(int x) {
    if (fa[x] != x) {
        fa[x] = find_fa(fa[x]);
    }

    return fa[x];
}

void merge_fa(int x, int y) {
    int fa_x = find_fa(x);
    int fa_y = find_fa(y);
    fa[fa_x] = fa_y;
    sum[fa_y] = sum[fa_x] + sum[fa_y];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        fa[b[i]] = -1;
    }

    maxx = -1;
    for (int i = n; i >= 1; i--) {
        fa[b[i]] = b[i];
        sum[b[i]] = a[b[i]];
        if (b[i] > 1 && fa[b[i] - 1] != -1) {
            merge_fa(b[i], b[i] - 1);
        }
        if (b[i] < n && fa[b[i] + 1] != -1) {
            merge_fa(b[i], b[i] + 1);
        }
        maxx = max(maxx, sum[find_fa(b[i])]);
        ans[i] = maxx;
    }

    for (int i = 2; i <= n; i++) {
        printf("%d\n", ans[i]);
    }
    printf("0\n");

    return 0;
}

发表于 2021-08-18 11:35:12 回复(0)

Java

今晚打老虎呢

二叉树用来存储各个区间，每次取出货物后，就把对应的树节点分裂

用哈希表来存储各个货物重量对应的个数，如果个数小于0的时候将其删除掉

用大顶堆来存储货物重量，堆顶就是答案

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 Main{

    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];
        }

        TreeNode root = new 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());
        }
    }
}

发表于 2021-03-23 14:07:19 回复(2)

Python

牛客404270893号

$O(n)$ 算法：逆序插入+ $O(1)$ 区间合并

n = int(input())
w = list(map(int, input().split()))
index = list(map(lambda x: int(x) - 1, input().split()))
d = {}  # 哈希表 key:(left, right, sum)
ans = [0] * n
maxHeap = 0
for i in range(n - 1, -1, -1):
    ans[i] = maxHeap
    L, R = index[i] - 1, index[i] + 1
#     print('i', L, R)
    if L in d and R in d:
        ll, lr, s1 = d[L]
        rl, rr, s2 = d[R]
        # 删除哈希表的端点
        d.pop(lr)
        d.pop(rl)
        d[ll] = d[rr] = (ll, rr, s1 + s2 + w[index[i]])
        # 删除和更新
        maxHeap = max(maxHeap, s1 + s2 + w[index[i]])
    elif L in d:
        ll, lr, s1 = d[L]
        # 删除哈希表的端点
        d.pop(lr)
        d[ll] = d[index[i]] = (ll, index[i], s1 + w[index[i]])
        # 删除和更新
        maxHeap = max(maxHeap, s1 + w[index[i]])
    elif R in d:
        rl, rr, s2 = d[R]
        # 删除哈希表的端点
        d.pop(rl)
        d[index[i]] = d[rr] = (index[i], rr, s2 + w[index[i]])
        # 删除和更新
        maxHeap = max(maxHeap, s2 + w[index[i]])
    else:
        d[index[i]] = (index[i], index[i], w[index[i]])
        maxHeap = max(maxHeap, w[index[i]])
print('\n'.join(str(n) for n in ans))

编辑于 2021-08-11 23:47:51 回复(1)

Java

深藏功与名的发呆爱好者很乐观

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

long[] sum = new long[n+2];

int[] nums = new int[n+2];

for (int i = 1; i <= n; i++) {

nums[i] = in.nextInt();

sum[i] = sum[i-1] + nums[i-1];

}

sum[n+1] = sum[n] + nums[n];

TreeSet<Integer> set = new TreeSet<>(new Comparator<Integer>() {

@Override

public int compare(Integer o1, Integer o2) {

return o1-o2;

}

});

set.add(0);

set.add(n+1);

for (int i = 1; i <= n; i++) {

int idx = in.nextInt();

set.add(idx);

int pre = 0;

long ans = 0;

for (Integer integer : set) {

ans = Math.max(ans, sum[integer] - sum[pre]-nums[pre]);

pre = integer;

}

System.out.println(ans);

}

请问一下这个如何优化呢

编辑于 2024-03-06 11:44:09 回复(0)

空城深处，住着空心、

num = int(input())
weights = list(map(int, input().split()))
order = list(map(lambda x:int(x)-1, input().split()))

re = [0 for i in range(num)]
left = [i for i in range(num)]
right = [i for i in range(num)]
ans = []
cur = 0
for i in order[::-1]:
ans.append(cur)
if not i:
re[0] = weights[0] + re[1]
elif i == num-1:
re[i] = weights[i] + re[i-1]
else:
re[i] = weights[i] + re[i-1] + re[i+1]
l, r = i, i
if i and re[i-1]:
l = left[i-1]
if i < num-1 and re[i+1]:
r = right[i+1]
right[l] = r
left[r] = l
re[l], re[r] = re[i], re[i]
cur = max(cur, re[i])
for i in ans[::-1]:
print(i)

发表于 2022-07-05 13:33:05 回复(0)

薛阿牛

不会啊大佬们救救我吧

发表于 2022-04-18 22:44:34 回复(0)

求求大厂或华为OFFER了

求大佬指导一下，AC60%，剩下的超时了

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int[] arr = new int[m];
        int[] sort = new int[m];
        int[] sum = new int[m+1];
        for (int i = 0; i < m; i++) {
            arr[i] = scanner.nextInt();
            sum[i+1] = sum[i]+arr[i];
        }
        for (int i = 0; i < m; i++) {
            sort[i] = scanner.nextInt();
        }
        Queue<QuJian> queue = new LinkedList<>();
        QuJian quJian = new QuJian(1,m,sum[m]);
        queue.offer(quJian);
        for (int i = 0; i < m; i++) {
            int len = queue.size();
            int maxNum = 0;
            int index = sort[i];
            for (int j = 0; j < len; j++) {
                QuJian temp = queue.poll();
                if (index<temp.start || index>temp.end){
                    maxNum = Math.max(temp.weight,maxNum);
                    queue.offer(temp);
                }else if (index == temp.start && index == temp.end){

                }else if (index==temp.start){
                    temp.weight = sum[temp.end]-sum[temp.start];
                    maxNum = Math.max(temp.weight,maxNum);
                    temp.start = temp.start+1;
                    queue.offer(temp);
                }else if (index==temp.end){
                    temp.weight = sum[temp.end-1]-sum[temp.start-1];
                    maxNum = Math.max(temp.weight,maxNum);
                    temp.end = temp.end-1;
                    queue.offer(temp);
                }else if (index>temp.start && index<temp.end){
                    //插入两个区间
                    int prevValue = sum[index-1]-sum[temp.start-1];
                    maxNum = Math.max(prevValue,maxNum);
                    queue.offer(new QuJian(temp.start,index-1,prevValue));
                    int behindValue = sum[temp.end]-sum[index];
                    maxNum = Math.max(behindValue,maxNum);
                    queue.offer(new QuJian(index+1,temp.end,behindValue));
                }
            }
            System.out.println(maxNum);
        }
    }
}

class QuJian{

    int start;
    int end;
    int weight;

    public QuJian(int start, int end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    public int getStart() {
        return start;
    }

    public void setStart(int start) {
        this.start = start;
    }

    public int getEnd() {
        return end;
    }

    public void setEnd(int end) {
        this.end = end;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }
}

发表于 2022-03-21 12:45:17 回复(0)

MechaVX

用了好多数组，大致想法是逆序插入物品，判断并合并区间，并用multiset来管理每一堆的重量。

#include <iostream>
#include <set>
#include <stack>
using namespace std;
int main(){
    int n;
    cin>>n;
    int*weight=new int[n+1];
    for(int i=1;i<=n;++i)
        cin>>weight[i];
    int*order=new int[n];
    for(int i=0;i<n;++i)
        cin>>order[i];
    int*beg_weight=new int[n+2]();
    int*beg_end=new int[n+1];
    for(int i=1;i<=n;++i)
        beg_end[i]=i;
    int*end_beg=new int[n+1]();
    for(int i=1;i<=n;++i)
        end_beg[i]=i;
    multiset<int> Set;
    stack<int> Stack;
    Stack.push(0);
    int index,lastend,nextbeg;
    for(int i=n-1;i;--i){
        index=order[i];
        lastend=index-1;
        nextbeg=index+1;
        int beg=index;
        int weight1=beg_weight[end_beg[lastend]];
        int weight2=beg_weight[nextbeg];
        int firstindex=index;
        if(weight1){
            Set.erase(Set.find(weight1));
            firstindex=end_beg[lastend];
            end_beg[index]=firstindex;
            if(weight2)
                beg_end[end_beg[lastend]]=beg_end[nextbeg];
            else
                beg_end[end_beg[lastend]]=index;
        }
        if(weight2){
            Set.erase(Set.find(weight2));
            beg_end[index]=beg_end[nextbeg];
            if(weight1)
                end_beg[beg_end[nextbeg]]=end_beg[lastend];
            else
                end_beg[beg_end[nextbeg]]=index;
        }
        int total=weight1+weight2+weight[index];
        Set.insert(total);
        beg_weight[firstindex]=total;
        Stack.push(*Set.rbegin());
    }
    while(!Stack.empty()){
        cout<<Stack.top()<<endl;
        Stack.pop();
    }
    return 0;
}

发表于 2022-02-12 17:01:45 回复(0)

Python

Ivan_2021

num = int(input())
weights = list(map(int, input().split()))
order = list(map(lambda x:int(x)-1, input().split()))

re = [0 for i in range(num)]
left = [i for i in range(num)]
right = [i for i in range(num)]
ans = []
cur = 0
for i in order[::-1]:
    ans.append(cur)
    if not i:
        re[0] = weights[0] + re[1]
    elif i == num-1:
        re[i] = weights[i] + re[i-1]
    else:
        re[i] = weights[i] + re[i-1] + re[i+1]
    l, r = i, i
    if i and re[i-1]:
        l = left[i-1]
    if i < num-1 and re[i+1]:
        r = right[i+1]
    right[l] = r
    left[r] = l
    re[l], re[r] = re[i], re[i]
    cur = max(cur, re[i])
for i in ans[::-1]:
    print(i)

记录一下一段能通过的python代码。

发表于 2021-09-30 17:41:47 回复(0)

yuzu_9497

超时

最后15分

n=int(input())
w=list(map(int,input().split()))
c=list(map(int,input().split()))
if n==1:
    print(0)
    exit()
dp=[[{'区间':[1,n],'值':sum(w)}]]
#dp[i]是列表，保存字典，表示拿走第i个物品后的每一堆的情况
for i in range(1,n+1):
    test=dp[i-1][0].get('区间')
    l=test[0]
    r=test[1]
    dp.append(dp[i-1].copy())
    if c[i-1]>r or c[i-1]<l:
        new=c[0:i]
        new.sort()
        cur=new.index(c[i-1])
        if cur==0:
            l=1
            r=new[cur+1]-1
        elif cur==i-1:
            l=new[cur-1]+1
            r=n
        else:
            l=new[cur-1]+1
            r=new[cur+1]-1
    for cur in range(len(dp[i])):
        if dp[i][cur].get('区间') == [l, r]:
            break
    if c[i-1]==l and c[i-1]!=r:
        dp[i].append({'区间':[l+1,r],'值':dp[i-1][cur].get('值')-w[c[i-1]-1]})
        dp[i].pop(cur)
        dp[i].sort(key=lambda x:x['值'],reverse=True)
    elif c[i-1]!=l and c[i-1]==r:
        dp[i].append({'区间':[l,r-1],'值':dp[i-1][cur].get('值')-w[c[i-1]-1]})
        dp[i].pop(cur)
        dp[i].sort(key=lambda x:x['值'],reverse=True)
    elif c[i-1]==l and c[i-1]==r:
        dp[i].pop(cur)
    else:
        dp[i].append({'区间':[l,c[i-1]-1],'值':sum(w[l-1:c[i-1]-1])})
        dp[i].append({'区间':[c[i-1]+1,r],'值':sum(w[c[i-1]:r])})
        dp[i].pop(cur)
        dp[i].sort(key=lambda x:x['值'],reverse=True)
for i in range(1,n):
    print(dp[i][0].get('值'))
print(0)

编辑于 2021-04-09 23:18:33 回复(0)

牛客972265768号

 这方法如何去优化时间，超时了！！！
 
public class Main {
       public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int a[] = new int[n];
            int b[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            for (int i = 0; i < n; i++) {
                b[i] = scanner.nextInt();
            }

            for (int i = 0; i < n; i++) {

                a[b[i] - 1] = 0;
                int max = 0;
                int tempMax = 0;

                for (int i1 : a) {
                    if (i1 != 0) {
                        tempMax += i1;
                    }
                    else    
                    {  
                        if (tempMax >= max)  max = tempMax; 
                        tempMax = 0;
                    } 
                }

                if (tempMax >= max) {
                    max = tempMax;
                }
                System.out.println(max);
 
            }


        }
}

发表于 2021-03-11 16:37:52 回复(2)