题目链接

物流中心包裹分拣

题目描述

在物流中心，一条传送带上有一系列包裹，每个包裹有一个目的地编号，形成一个整数数组。任务是将这串包裹划分成最多数量的连续“批次”。

划分规则： 对每个批次单独进行从小到大排序，然后按原始批次顺序将排序后的批次拼接起来。最终得到的序列必须与将所有包裹一次性进行全局排序的结果完全一致。

任务： 找出满足上述条件的最大批次数。

输入描述：

  • 一行由空格隔开的正整数，代表传送带上包裹的目的地编号。

输出描述：

  • 一个整数，代表最多可以划分的批次数。

解题思路

本题的目标是找到一个数组最多可以被分割成多少个连续的子数组（批次），使得对每个子数组独立排序后，按原顺序拼接起来的结果等于整个数组排序后的结果。

核心条件

要满足题目的要求，一个划分方案必须保证，对于任意两个相邻的批次 和 ，批次 中的所有元素都必须小于或等于批次 中的所有元素。如果这个条件对所有相邻批次都成立，那么将它们各自排序后拼接，其结果必然是全局有序的。

这个条件可以进一步简化：我们可以在索引 处进行一次切割，形成批次 arr[0...i] 和 arr[i+1...N-1] 的充要条件是：前一个批次中的最大值，小于或等于后一个批次中的最小值。 即： max(arr[0...i]) <= min(arr[i+1...N-1])。

优化算法

为了找到最多的批次数，我们应该在每一个满足上述条件的位置都进行切割。直接为每个可能的切割点 计算前缀最大值和后缀最小值，时间复杂度会是 。我们可以通过预计算来优化这个过程。

  1. 预计算前缀最大值：创建一个数组 left_max，其中 left_max[i] 存储 arr[0...i] 区间内的最大值。这可以通过一次从左到右的遍历完成。 left_max[i] = max(left_max[i-1], arr[i])

  2. 预计算后缀最小值：创建一个数组 right_min，其中 right_min[i] 存储 arr[i...N-1] 区间内的最小值。这可以通过一次从右到左的遍历完成。 right_min[i] = min(right_min[i+1], arr[i])

  3. 统计批次数：

    • 初始化批次数 chunks = 1（因为至少有一个批次）。
    • 遍历所有可能的切割点，即从索引 到 。
    • 在每个位置 ，检查是否满足切割条件：left_max[i] <= right_min[i+1]。
    • 如果满足，说明可以在 和 之间切一刀，从而增加一个批次，因此 chunks 加 1。
    • 遍历结束后，chunks 就是最多可以划分的批次数。

这种方法通过三次线性扫描完成了计算，总时间复杂度为 ，空间复杂度为 用于存储预计算的数组。

代码

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

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

    string line;
    getline(cin, line);
    stringstream ss(line);
    
    vector<int> arr;
    int num;
    while (ss >> num) {
        arr.push_back(num);
    }

    int n = arr.size();
    if (n <= 1) {
        cout << n << endl;
        return 0;
    }

    vector<int> left_max(n);
    left_max[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        left_max[i] = max(left_max[i - 1], arr[i]);
    }

    vector<int> right_min(n);
    right_min[n - 1] = arr[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        right_min[i] = min(right_min[i + 1], arr[i]);
    }

    int chunks = 1;
    for (int i = 0; i < n - 1; ++i) {
        if (left_max[i] <= right_min[i + 1]) {
            chunks++;
        }
    }

    cout << chunks << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] parts = line.split(" ");
        
        List<Integer> arrList = new ArrayList<>();
        for(String part : parts) {
            arrList.add(Integer.parseInt(part));
        }
        
        int n = arrList.size();
        if (n <= 1) {
            System.out.println(n);
            return;
        }

        int[] arr = arrList.stream().mapToInt(i->i).toArray();

        int[] leftMax = new int[n];
        leftMax[0] = arr[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], arr[i]);
        }

        int[] rightMin = new int[n];
        rightMin[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMin[i] = Math.min(rightMin[i + 1], arr[i]);
        }

        int chunks = 1;
        for (int i = 0; i < n - 1; i++) {
            if (leftMax[i] <= rightMin[i + 1]) {
                chunks++;
            }
        }

        System.out.println(chunks);
    }
}

def solve():
    arr = list(map(int, input().split()))
    n = len(arr)

    if n <= 1:
        print(n)
        return

    # 计算前缀最大值
    left_max = [0] * n
    left_max[0] = arr[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], arr[i])

    # 计算后缀最小值
    right_min = [0] * n
    right_min[n - 1] = arr[n - 1]
    for i in range(n - 2, -1, -1):
        right_min[i] = min(right_min[i + 1], arr[i])

    # 统计可以切割的次数
    chunks = 1
    for i in range(n - 1):
        if left_max[i] <= right_min[i + 1]:
            chunks += 1
            
    print(chunks)

solve()

算法及复杂度

  • 算法：本题采用了一种基于前缀最大值和后缀最小值的贪心策略。通过两次线性扫描预计算出每个位置左侧的最大值和右侧的最小值，然后在第三次扫描中，检查每一个可能的分割点是否满足 max(left_part) <= min(right_part) 的条件。为了获得最大批次数，我们在每个满足条件的点都进行分割。

  • 时间复杂度：，其中 是包裹的总数。算法包含三次独立的线性遍历（一次计算前缀最大值，一次计算后缀最小值，一次检查分割点），每次遍历的时间复杂度都是 ，因此总时间复杂度为 。

  • 空间复杂度：。需要额外的空间来存储前缀最大值数组和后缀最小值数组，每个数组的大小都为 。