题解

题目描述

某地发生地震道路被毁，只有一条路可走，多个市派出车队运送物资，每个市提供的物资车数不一样，到达灾区后需排队依次进入，各市车队组成一个数组 $cars[]$，队首的市的物资车数为 $cars[0]$，以此类推。

同时灾区临时营地中的多人排队领取物资，组成一个领物资队伍，表示为数组 $requires[]$，排在第 $1$ 名的需求车数为 $requires[0]$，以此类推。

为尽快缩减营地中排队领物资队伍的长度，制定了一套发放规则：

1. 假设当前进入营地的市车队运来的物资车数为 $K$。
2. 在领取队伍中，找到需求和小于等于 $K$ 的最长的一个子队伍，即连续子序列，其和小于等于 $K$（仅包含一个成员也是可以的），将当前营地中的所有市车队物资分配给这个子序列中的所有人，此为完成一次分配。
3. 若未找到任何满足分配条件的人，则放入下一个市车队进入营地，与营地中已有的物资车累加起来，重新进行分配计算。

问：按照此规则发放，总计进行了多少次分配，有多少人不能领到物资？

思路

1. 维护当前可用物资：设变量 $K$ 表示当前营地中累计的物资车数，初始时取 $cars[0]$。
2. 寻找最长子序列：对于当前 $K$，在 $requires$ 中寻找和不超过 $K$ 的最长连续子数组。可使用滑动窗口：
   • 设左右指针 $l=0$，遍历右指针 $r$ 从 $0$ 到 $n-1$，维护窗口和 $sum$。
   • 当 $sum + requires[r] \le K$ 时，扩展窗口；否则，收缩左端直到 $sum + requires[r] \le K$。
   • 记录最大窗口长度 $maxLen$ 及其起始位置 $start$。
3. 执行分配或累加：
   • 若 $maxLen > 0$，则从 $requires$ 中删除该区间 $[start, start+maxLen-1]$，分配次数加 $1$，重置 $K = cars[nextCity]$ 并继续（或若无下一市队，则退出）。
   • 否则，将下一个市的物资加入 $K$，继续寻找，直到用完所有市车队或能分配为止。
4. 结果统计：统计分配次数和剩余 $requires$ 的长度即未分配人数。

时间复杂度：

• 外循环遍历市队 $O(m)$，每次查最长子序列 $O(n)$，总计 $O(mn)$，在 $m\le200$，$n\le10^5$ 时可接受（最坏约 $2\times10^7$ 次操作）。

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> cars;
    vector<int> requires;
    int x;
    // 读入 cars 数组
    string line;
    if (!getline(cin, line)) return 0;
    istringstream ic(line);
    while (ic >> x) cars.push_back(x);
    // 读入 requires 数组
    if (!getline(cin, line)) return 0;
    istringstream ir(line);
    while (ir >> x) requires.push_back(x);

    int m = cars.size(), n = requires.size();
    int city = 0;         // 当前市队索引
    long long K = cars[city];  // 当前可用物资
    int ops = 0;         // 分配次数

    while (true) {
        int l = 0;
        long long sum = 0;
        int maxLen = 0, start = -1;
        // 滑动窗口寻找最长子序列
        for (int r = 0; r < n; ++r) {
            sum += requires[r];
            while (l <= r && sum > K) {
                sum -= requires[l++];
            }
            if (r - l + 1 > maxLen) {
                maxLen = r - l + 1;
                start = l;
            }
        }
        if (maxLen > 0) {
            // 执行一次分配
            requires.erase(requires.begin() + start,
                           requires.begin() + start + maxLen);
            n -= maxLen;
            ops++;
            city++;
            if (city >= m) break;
            K = cars[city];
        } else {
            // 无法分配，累加下一市资源
            city++;
            if (city >= m) break;
            K += cars[city];
        }
    }
    // 输出分配次数和剩余人数
    cout << ops << " " << requires.size();
    return 0;
}

Python

from collections import deque

# 读入
cars = list(map(int, input().split()))
requires = list(map(int, input().split()))

m, n = len(cars), len(requires)
city = 0
K = cars[city]
ops = 0

while True:
    l = 0
    curr_sum = 0
    max_len, start = 0, -1
    # 滑动窗口
    for r in range(len(requires)):
        curr_sum += requires[r]
        while l <= r and curr_sum > K:
            curr_sum -= requires[l]
            l += 1
        if r - l + 1 > max_len:
            max_len = r - l + 1
            start = l
    if max_len > 0:
        # 删除分配区间
        del requires[start:start+max_len]
        ops += 1
        city += 1
        if city >= m:
            break
        K = cars[city]
    else:
        city += 1
        if city >= m:
            break
        K += cars[city]

print(ops, len(requires))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s1 = sc.nextLine().split(" ");
        String[] s2 = sc.nextLine().split(" ");
        List<Integer> cars = new ArrayList<>();
        List<Integer> req = new ArrayList<>();
        for (String s : s1) cars.add(Integer.parseInt(s));
        for (String s : s2) req.add(Integer.parseInt(s));

        int m = cars.size();
        int city = 0;
        long K = cars.get(city);
        int ops = 0;
        
        while (true) {
            int l = 0;
            long sum = 0;
            int maxLen = 0, start = -1;
            // 滑动窗口寻找最长子序列
            for (int r = 0; r < req.size(); r++) {
                sum += req.get(r);
                while (l <= r && sum > K) {
                    sum -= req.get(l);
                    l++;
                }
                if (r - l + 1 > maxLen) {
                    maxLen = r - l + 1;
                    start = l;
                }
            }
            if (maxLen > 0) {
                // 执行一次分配
                for (int i = 0; i < maxLen; i++) {
                    req.remove(start);
                }
                ops++;
                city++;
                if (city >= m) break;
                K = cars.get(city);
            } else {
                city++;
                if (city >= m) break;
                K += cars.get(city);
            }
        }
        System.out.println(ops + " " + req.size());
    }
}

题目内容

某地发生地震道路被毁，只有一条路可走，多个市派出车队运送物资，每个市提供的物资车数不一样，到达灾区后需排队依次进入，各市车队组成一个数组$cars[]$，队首的市的物资车数为$cars[0]$，以此类推。

同时灾区临时营地中的多人排队领取物资，组成一个领物资队伍，表示为数组$requires[]$，排在第$1$名的需求车数为的为$requires[0]$，以此类推。

为尽快缩减营地中排队领物资队伍的长度，制定了一套发放规则: 假设当前进入营地的市车队运来的物资车数为K

1、在领取队伍中，找到需求和小于等于K的最长的一个子队伍，即子序列的和小于等于$K$的最长连续子序列(仅包含一个成员也是可以的)，将当前营地中的所有市车队物资分配给这个子序列中的所有人，此为完成一次分配。

2、若未找到任何人满足分配条件，则放入下一个市车队进入营地，与营地中已有的物资车累加起来，重新进行分配计算。问按照此规则发放，总计进行了多少次分配，有多少人不能领到物资?

输入描述

输入为两行:

第$1$行为各市物资车数的数组$cars$，空格分隔，$car[i]$表示编号$i(i<=200)$的市运来的物资车数$(1 <= car[i] <=5000)$。例如:$3\ 5\ 7\ 9\ 3\ 2\ 1$

第$2$行为需求数组$requires$数，空格分隔，$requires[]$表示编号$j( j<=10^5)$的人的需求数$(1 <= requires[j ]<=100)$。例如:$1\ 2\ 4\ 5\ 2$非法输入返回$-1$

输出描述

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

例如:

$2\ 0$

表示总计分配次数为2，未分配到物资人数为$0$

样例1

输入

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

输出

4 1

说明

第$1$次分配:通过计算得到小于等于$8$的最长子序列为$1,2,3,1$，因此将营地中物资$8$车全部分配给$1,2,3,1$，完成第一次分配。

第$2$次分配:$7$车物资分给$1\ 2\ 4$

第$3$次分配:$9$车物资分给$4,5$

第$4$次分配:$6$车物资分给$6$

此时市队伍剩余$2,1$，且2在营地中待分配，领物资队伍剩余$7$。进行分配计算，得出无法进行分配，因此将下一个市进入营地，此时营地中累计物资车数为$3$，进行分配计算，仍无法分配且市队伍已无市可用，流程结束。

综上，总计成功分配了$4$次，剩余$1$个人，输出$4\ 1$

样例2

输入

8
4 2 2 8 2 2 2 1

输出

1 4

说明

分析小于等于$8$的子序列:相对较长的有这两个，$4\ 2\ 2,2\ 2\ 2\ 1$，因$2\ 2\ 2\ 1$长度更长，因此进行实际分配，领物资队伍剩余$4\ 2\ 2\ 8$。累计分配了$1$次。输出$1\ 4$

样例3

输入

2 2 2 2
8 9 8 8

输出

1 3

说明

前$4$个市的物资分配给第一个人，只进行了$1$次分配，剩余$3$个人，因此输出$1\ 3$