题目大意

给定一个长度为 n 的序列，问如何将该序列归类为最少的连续递增序列。连续递增序列满足：对于序列中的任意 i，满足 a[i] = a[i-1] + 1。

注意原序列不能被任意打乱

题解：贪心 + 哈希表

思路分析：

题目要求我们计算最少的发送源个数，基于题目的描述，发送源的数据包序列号是连续递增的。如果数据包序列号出现不连续或重复的情况，那么这些数据包必然来自于多个发送源。我们的目标是通过扫描一遍输入序列号，计算出最少的发送源个数。

我们可以使用贪心算法和哈希表来高效解决这个问题。

具体思路：

我们维护一个哈希表 cnt，cnt[x] 代表当前有多少个以序列号 x 结尾的递增子序列。然后逐个处理输入序列号 a[i]。

对于每个序列号 x，有以下两种情况：

1. x 前面没有以 x-1 结尾的序列：
   如果哈希表中 cnt[x-1] 的值为 0，说明当前序列号 x 需要作为新的递增子序列的开头，因此我们需要新开一个发送源，ans 加 1。

2. x 前面有以 x-1 结尾的序列：
   如果 cnt[x-1] 的值大于 0，说明有一个子序列是以 x-1 结尾的，我们可以将 x 加入这个子序列，这样并不需要增加新的发送源。同时我们更新哈希表，将 cnt[x-1] 减 1，表示该子序列不再以 x-1 结尾，而是改为以 x 结尾，所以 cnt[x] 需要加 1。

通过以上两步的操作，我们可以在一次遍历中动态地计算出最少的发送源个数。

时间复杂度分析：

• 遍历数组的时间复杂度为 $O(n)$，其中 $n$ 是数组的长度。
• 使用哈希表 cnt 进行查询和更新的时间复杂度为均摊 $O(1)$。

因此整体时间复杂度为 $O(n)$，可以在输入数据范围较大的情况下高效处理问题。

代码

Python 实现

from collections import defaultdict

# 输入处理
n = int(input())  # 序列长度
a = list(map(int, input().split()))  # 序列

cnt = defaultdict(int)  # 记录以某个数结尾的递增序列的数量
ans = 0  # 记录最少的连续递增序列的数量

# 遍历序列
for x in a:
    # 如果没有以x-1结尾的递增序列，那么x需要开辟一个新的递增序列
    if cnt[x - 1] == 0:
        ans += 1  # 答案增加一个新的序列
    else:
        # 如果有以x-1结尾的递增序列，那么将x加入该序列
        cnt[x - 1] -= 1  # 以x-1结尾的序列少一个
    cnt[x] += 1  # 更新以x结尾的序列数量

# 输出结果
print(ans)

Java 实现

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 输入处理
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        // 使用HashMap来存储 cnt[x]，即以x结尾的递增序列的数量
        HashMap<Integer, Integer> cnt = new HashMap<>();
        int ans = 0; // 记录最少的连续递增序列的数量

        for (int x : a) {
            // 如果没有以x-1结尾的序列，则x需要开辟一个新的序列
            if (!cnt.containsKey(x - 1) || cnt.get(x - 1) == 0) {
                ans++;
            } else {
                // 如果有以x-1结尾的序列，则将x加入该序列
                cnt.put(x - 1, cnt.get(x - 1) - 1);
            }
            // 更新以x结尾的序列数量
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        }

        // 输出结果
        System.out.println(ans);
    }
}

C++ 实现

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    // 输入处理
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 使用unordered_map来存储cnt[x]，即以x结尾的递增序列的数量
    unordered_map<int, int> cnt;
    int ans = 0; // 记录最少的连续递增序列的数量

    for (int i = 0; i < n; i++) {
        int x = a[i];
        // 如果没有以x-1结尾的序列，则x需要开辟一个新的序列
        if (cnt[x - 1] == 0) {
            ans++;
        } else {
            // 如果有以x-1结尾的序列，则将x加入该序列
            cnt[x - 1]--;
        }
        // 更新以x结尾的序列数量
        cnt[x]++;
    }

    // 输出结果
    cout << ans << endl;

    return 0;
}