2025.05.14华为机考笔试题-第三题-300分

📌 点击直达笔试专栏 👉《大厂笔试突围》

💻 春秋招笔试突围在线OJ 👉 笔试突围OJ

03. 物资分配优化系统

问题描述

卢小姐负责一个灾后物资分配中心。在一次自然灾害后，由于道路中断，只有一条通道可用于物资运输。多个援助点派出车队运送物资，组成一个车队数组 $cars[]$，其中 $cars[i]$ 表示第 $i$ 个援助点提供的物资车数。

同时，灾区临时安置点内有许多灾民正在排队等待领取物资，组成一个需求队列，表示为数组 $requires[]$，其中 $requires[j]$ 表示排在第 $j$ 位的灾民所需的物资车数。

为了高效分配物资并尽快减少等待队伍长度，物资分配中心制定了以下规则：

假设当前进入分配中心的援助点车队运来的物资车数为 $K$：

1. 在等待队伍中，寻找需求总和小于等于 $K$ 的最长连续子队伍（可以只包含一个人），将当前分配中心中的所有物资分配给这个子队伍中的所有人，这算作一次完整分配。

2. 若未找到任何符合条件的队伍，则让下一个援助点的车队进入分配中心，将其物资数量与分配中心已有的物资车数累加，然后重新进行分配计算。

根据上述规则，请计算总共能完成多少次分配，以及最终有多少灾民无法领到物资。

输入格式

输入包含两行：

第 $1$ 行为各援助点物资车数的数组 $cars$，数值间用空格分隔，$cars[i]$ 表示编号 $i(i\le 200)$ 的援助点运来的物资车数 $(1\le cars[i]\le 5000)$。

第 $2$ 行为需求数组 $requires$，数值间用空格分隔，$requires[j]$ 表示编号 $j(j\le 10^5)$ 的灾民的需求数 $(1\le requires[j]\le 100)$。

非法输入返回 $-1$。

输出格式

输出分配总次数和不能分到物资的灾民数，用空格分隔。

样例输入

8 7 3 6 6 2 1
7 1 2 4 6 1 2 3 1 4 5

8
4 2 2 8 2 2 2 1

2 2 2 2
8 9 8 8

样例输出

4 1

1 4

1 3

数据范围

• $1\le cars[i]\le 5000$
• $1\le requires[j]\le 100$
• $援助点数量\le 200$
• $灾民数量\le 10^5$

题解

这道题目的核心是滑动窗口算法的应用，需要在请求队列中找到和不超过当前可用物资 K 的最长连续子序列。

解题思路如下：

1. 首先维护当前可用物资数量 K（初始为0）。

2. 对于等待队列，我们需要找到和小于等于 K 的最长连续子序列。这可以通过滑动窗口方法实现：

   • 使用左右指针表示窗口的左右边界。
   • 右指针不断向右扩展窗口，累加窗口内的需求和。
   • 当窗口内需求和超过 K 时，左指针向右移动缩小窗口，直到窗口内需求和不超过 K。
   • 在过程中记录最长的有效窗口。

3. 找到最长子序列后：

   • 如果存在有效子序列（长度 > 0），将其从等待队列中移除，完成一次分配，重置 K 为 0。
   • 如果不存在有效子序列，则将下一个援助点的车队加入，累加 K 值，再重新进行分配计算。

4. 重复上述过程，直到所有援助点的车队都已使用，且无法继续分配。

时间复杂度分析：

• 在最坏情况下，我们需要遍历所有援助点和所有灾民。
• 对于每个援助点，我们最多需要扫描整个等待队列一次（滑动窗口）。
• 因此总体时间复杂度为 O(n * m)，其中 n 是援助点数量，m 是灾民数量。
• 在实际情况下，由于每次成功分配后都会从等待队列中移除一部分人，实际复杂度通常低于理论上限。

空间复杂度：O(m)，主要用于存储等待队列。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

def main():
    try:
        # 读取输入
        cars = list(map(int, input().split()))
        reqs = list(map(int, input().split()))
        
        icar = 0
        ncars = len(cars)
        k = 0  # 当前可用物资数量
        alloc = 0  # 分配次数
        
        # 持续分配直到无法继续
        while True:
            if not reqs:  # 没有等待的人了，结束
                break
                
            # 寻找和小于等于k的最长连续子序列
            best_len = 0
            best_l = -1
            sum_val = 0
            l = 0
            
            for r in range(len(reqs)):
                sum_val += reqs[r]
                # 如果总和超过k，移动左指针
                while l <= r and sum_val > k:
                    sum_val -= reqs[l]
                    l += 1
                    
                # 更新最长子序列
                if sum_val <= k and r - l + 1 > best_len:
                    best_len = r - l + 1
                    best_l = l
            
            # 找到了有效子序列，进行分配
            if best_len > 0:
                # 删除分配的子序列
                reqs = reqs[:best_l] + reqs[best_l + best_len:]
                alloc += 1
                k = 0  # 重置可用物资
            else:
                # 没有找到有效子序列，尝试添加下一个援助点
                if icar < ncars:
                    k += cars[icar]
                    icar += 1
                else:
                    break  # 无更多援助点，结束
        
        # 输出结果
        print(f"{alloc} {len(reqs)}")
        
    except Exception:
        print("-1")

if __name__ == "__main__":
    main()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string line;
    vector<int> cars;
    // 读取第一行：援助点物资车数
    if (!getline(cin, line)) return 0;
    {
        istringstream iss(line);
        int x;
        while (iss >> x) cars.push_back(x);
    }
    
    // 读取第二行：需求数组
    vector<int> reqs;
    if (!getline(cin, line)) { cout << "-1"; return 0; }
    {
        istringstream iss(line);
        int x;
        while (iss >> x) reqs.push_back(x);
    }
    
    int nCars = cars.size();
    int iCar = 0;
    long long k = 0;  // 当前可用物资
    int allocs = 0;   // 分配次数
    
    while (true) {
        // 所有人都已分配完毕
        if (reqs.empty()) break;
        
        // 寻找和小于等于k的最长连续子序列
        int bestLen = 0, bestL = -1;
        long long sum = 0;
        int l = 0;
        
        for (int r = 0; r < reqs.size(); r++) {
            sum += reqs[r];
            // 总和超过k，左指针右移
            while (l <= r && sum > k) sum -= reqs[l++];
            
            // 更新最长子序列
            if (sum <= k && r - l + 1 > bestLen) {
                bestLen = r - l + 1;
                bestL = l;
            }
        }
        
        // 找到有效子序列，进行分配
        if (bestLen > 0) {
            reqs.erase(reqs.begin() + bestL, reqs.begin() + bestL + bestLen);
            allocs++;
            k = 0;  // 重置可用物资
        } else {
            // 尝试添加下一个援助点
            if (iCar < nCars) {
                k += cars[iCar++];
            } else break;  // 无更多援助点，结束
        }
    }
    
    // 输出结果
    cout << allocs << " " << reqs.size();
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        try {
            // 读取第一行：援助点物资车数
            String[] carsStr = sc.nextLine().split(" ");
            int[] cars = new int[carsStr.length];
            for (int i = 0; i < carsStr.length; i++) {
                cars[i] = Integer.parseInt(carsStr[i]);
            }
            
            // 读取第二行：需求数组
            String[] reqsStr = sc.nextLine().split(" ");
            List<Integer> reqs = new ArrayList<>();
            for (String s : reqsStr) {
                reqs.add(Integer.parseInt(s));
            }
            
            int nCars = cars.length;
            int iCar = 0;
            long k = 0;  // 当前可用物资
            int allocs = 0;  // 分配次数
            
            while (true) {
                // 所有人都已分配完毕
                if (reqs.isEmpty()) break;
                
                // 寻找和小于等于k的最长连续子序列
                int bestLen = 0, bestL = -1;
                long sum = 0;
                int l = 0;
                
                for (int r = 0; r < reqs.size(); r++) {
                    sum += reqs.get(r);
                    // 总和超过k，左指针右移
                    while (l <= r && sum > k) {
                        sum -= reqs.get(l++);
                    }
                    
                    // 更新最长子序列
                    if (sum <= k && r - l + 1 > bestLen) {
                        bestLen = r - l + 1;
                        bestL = l;
                    }
                }
                
                // 找到有效子序列，进行分配
                if (bestLen > 0) {
                    // 移除已分配的子序列
                    for (int i = 0; i < bestLen; i++) {
                        reqs.remove(bestL);
                    }
                    allocs++;
                    k = 0;  // 重置可用物资
                } else {
                    // 尝试添加下一个援助点
                    if (iCar < nCars) {
                        k += cars[iCar++];
                    } else break;  // 无更多援助点，结束
                }
            }
            
            // 输出结果
            System.out.println(allocs + " " + reqs.size());
            
        } catch (Exception e) {
            System.out.println("-1");
        }
    }
}