物流中心包裹分拣

题意

传送带上有 $n$ 个包裹，每个包裹标有一个目的地编号。要求将这些包裹划分成最多数量的连续批次，使得每个批次独立排序后，按原先批次顺序拼接起来的结果与全局排序的结果一致。

思路

什么时候可以在位置 $i$ 后面切一刀？当且仅当前 $i+1$ 个元素的多重集合恰好等于全局排序后前 $i+1$ 个元素的多重集合。换句话说，前 $i+1$ 个位置已经"集齐"了它们排序后应该拥有的所有元素，不多也不少。

怎么高效判断两个多重集合相等？维护一个频次差值表 diff：从左到右扫描，每到位置 $i$ ，把原数组 a[i] 的计数 $+1$ ，把排序数组 s[i] 的计数 $-1$ 。同时用一个变量 nonzero 记录 diff 中有多少个键的值不为零。当 nonzero == 0 时，说明前缀的多重集合完全匹配，可以在这里切一刀，答案加一。

以示例 1 [2, 1, 3, 4, 4, 5] 为例，排序后 [1, 2, 3, 4, 4, 5]：

位置 $i$	加入 `a[i]`	减去 `s[i]`	`nonzero`	可切？
0	+2	-1	2	否
1	+1	-2	0	是
2	+3	-3	0	是
3	+4	-4	0	是
4	+4	-4	0	是
5	+5	-5	0	是

共 5 次切割，输出 5。

示例 2 [5, 4, 3, 2, 1]，排序后 [1, 2, 3, 4, 5]，直到最后一个位置 nonzero 才变为 0，所以只能输出 1。

代码

C++
Java
Python3
JavaScript

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

int main(){
    vector<int> a;
    int x;
    while(scanf("%d", &x) == 1) a.push_back(x);
    int n = a.size();
    vector<int> s(a);
    sort(s.begin(), s.end());
    unordered_map<int,int> diff;
    int nonzero = 0, ans = 0;
    for(int i = 0; i < n; i++){
        if(diff[a[i]] == 0) nonzero++;
        diff[a[i]]++;
        if(diff[a[i]] == 0) nonzero--;
        if(diff[s[i]] == 0) nonzero++;
        diff[s[i]]--;
        if(diff[s[i]] == 0) nonzero--;
        if(nonzero == 0) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine().trim();
        String[] parts = line.split("\\s+");
        int n = parts.length;
        int[] a = new int[n];
        int[] s = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(parts[i]);
            s[i] = a[i];
        }
        Arrays.sort(s);
        HashMap<Integer, Integer> diff = new HashMap<>();
        int nonzero = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            int da = diff.getOrDefault(a[i], 0);
            if (da == 0) nonzero++;
            da++;
            if (da == 0) nonzero--;
            diff.put(a[i], da);

            int ds = diff.getOrDefault(s[i], 0);
            if (ds == 0) nonzero++;
            ds--;
            if (ds == 0) nonzero--;
            diff.put(s[i], ds);

            if (nonzero == 0) ans++;
        }
        System.out.println(ans);
    }
}

import sys
from collections import defaultdict

def main():
    a = list(map(int, sys.stdin.read().split()))
    s = sorted(a)
    diff = defaultdict(int)
    nonzero = 0
    ans = 0
    for i in range(len(a)):
        if diff[a[i]] == 0:
            nonzero += 1
        diff[a[i]] += 1
        if diff[a[i]] == 0:
            nonzero -= 1
        if diff[s[i]] == 0:
            nonzero += 1
        diff[s[i]] -= 1
        if diff[s[i]] == 0:
            nonzero -= 1
        if nonzero == 0:
            ans += 1
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
let lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const a = lines[0].split(/\s+/).map(Number);
    const n = a.length;
    const s = [...a].sort((x, y) => x - y);
    const diff = new Map();
    let nonzero = 0, ans = 0;
    for (let i = 0; i < n; i++) {
        let da = diff.get(a[i]) || 0;
        if (da === 0) nonzero++;
        da++;
        if (da === 0) nonzero--;
        diff.set(a[i], da);

        let ds = diff.get(s[i]) || 0;
        if (ds === 0) nonzero++;
        ds--;
        if (ds === 0) nonzero--;
        diff.set(s[i], ds);

        if (nonzero === 0) ans++;
    }
    console.log(ans);
});

复杂度分析

时间复杂度： $O(n \log n)$ ，排序为主要开销，扫描一遍为 $O(n)$ 。
空间复杂度： $O(n)$ ，存储排序数组和哈希表。