题面描述

塔子哥需要管理 $10^5$ 个通道，当用户输入 $-1$ 时，将分配一个未被使用的最小通道编号；若输入有效通道编号，则回收该通道。你需要计算经过若干操作后，下一次申请时可以获得的通道编号，若无可用通道则返回 $-1$。输入包括操作次数 $n$ 和 $n$ 个操作数，输出为下一个可用的通道编号。

思路：模拟/小根堆

我们可以把set当作小根堆来使用，用来模拟这个问题，首先把$10^5$个通道编号全部按顺序入队（通道编号下标从0开始），这样队头元素就是编号最小的通道

• 用户输出-1，直接弹出队头元素(取出set的开头元素)
• 用户输出为$x$，把$x$直接放进去set即可 最终输出的结果即为set的队头元素 上述模拟的过程，是使用set集合的思想，也可以直接使用优先队列，优先队列是小根堆，这样堆顶就是编号最小的通道

解决思路

1. 初始化：

   • 使用一个 set（集合）来存储所有可用的通道编号，初始化时将 $0$ 到 $100000$ 的所有编号插入集合中。由于集合会自动保持元素的有序性，集合的头元素即为当前最小的空闲通道编号。

2. 处理用户输入：

   • 当用户输入 -1 时，表示需要分配一个通道编号，我们从集合中取出并删除最小的元素。
   • 当用户输入一个有效的通道编号 x 时，表示释放该通道编号，我们将其添加回集合中。

3. 输出结果：

   • 在所有操作完成后，如果集合中仍有元素，输出集合的头元素（即最小的可用通道编号）；如果集合为空，输出 -1。

复杂度分析

• 时间复杂度：

  • 插入和删除操作的时间复杂度均为 $O(\log m)$，其中 $m$ 是当前集合中的元素个数。
  • 在最坏情况下（每次操作都为 -1），集合的操作会进行 $n$ 次，因此总体复杂度为 $O(n \log m)$，其中 $m$ 最多为 $100001$。

• 空间复杂度：

  • 需要额外的空间存储集合，最坏情况下需要存储 $100001$ 个通道编号，因此空间复杂度为 $O(m)$。

时间复杂度

$O(nlogn)$

代码

C++

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

int main() {
    int n;  // 输入操作次数
    cin >> n;

    set<int> free;   // 存储空闲的通道编号

    // 初始化空闲通道集合，将编号从 0 到 100000 加入集合
    for (int i = 0; i <= 100000; i++) {
        free.insert(i);
    }

    // 处理每个用户操作
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;  // 读取用户输入

        if (x == -1) {
            // 输入为 -1 时，分配最小编号的空闲通道
            if (!free.empty()) {  // 检查集合是否为空
                int alloc = *free.begin();  // 获取最小的空闲通道编号
                free.erase(alloc);          // 从空闲集合中删除该通道编号
            }
        } else {
            // 输入为有效通道编号时，释放该通道
            free.insert(x);  // 将通道编号 x 加入空闲集合
        }
    }

    // 输出下一个可分配的通道编号，如果没有可用通道则输出 -1
    if (!free.empty()) {  // 检查集合是否为空
        cout << *free.begin() << '\n';  // 输出集合的最小元素
    } else {
        cout << -1 << '\n';  // 输出 -1 表示没有可用通道
    }

    return 0;
}

python代码

import heapq

# 读取输入操作次数
n = int(input().strip())

# 使用最小堆来存储空闲的通道编号
free = list(range(100001))  # 初始化空闲通道列表
heapq.heapify(free)         # 将列表转化为最小堆

# 使用集合来追踪已经分配出去的通道，避免重复释放
busy_set = set()

# 读取所有操作
operations = list(map(int, input().strip().split()))

for x in operations:
    if x == -1:
        # 输入为 -1 时，分配最小编号的空闲通道
        if free:
            alloc = heapq.heappop(free)  # 从堆中获取并删除最小值
            busy_set.add(alloc)          # 标记该通道为已分配
    else:
        # 输入为有效通道编号时，释放该通道
        if x in busy_set:
            busy_set.remove(x)           # 从已分配集合中删除
            heapq.heappush(free, x)      # 重新将该通道编号加入堆中

# 输出下一个可分配的通道编号，如果没有可用通道则输出 -1
if free:
    # 从堆中获取最小值，同时确保该通道编号没有在 busy_set 中（防止重复分配）
    while free and free[0] in busy_set:
        heapq.heappop(free)  # 移除 busy_set 中的通道编号，直到找到有效通道

    # 如果堆中还有空闲通道，输出最小编号
    if free:
        print(free[0])
    else:
        print(-1)
else:
    print(-1)

Java代码

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入操作次数
        int n = sc.nextInt();

        // 存储空闲的通道编号
        Set<Integer> free = new TreeSet<>();

        // 初始化空闲通道集合，将编号从 0 到 100000 加入集合
        for (int i = 0; i <= 100000; i++) {
            free.add(i);
        }

        // 处理每个用户操作
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();

            if (x == -1) {
                // 输入为 -1 时，分配最小编号的空闲通道
                if (!free.isEmpty()) {
                    int alloc = free.iterator().next();  // 获取最小的空闲通道编号
                    free.remove(alloc);                  // 从空闲集合中删除
                }
            } else {
                // 输入为有效通道编号时，释放该通道
                free.add(x);  // 加入空闲集合
            }
        }

        // 输出下一个可分配的通道编号，如果没有可用通道则输出 -1
        if (!free.isEmpty()) {
            System.out.println(free.iterator().next());
        } else {
            System.out.println(-1);
        }

        sc.close();
    }
}

题目描述

小明将对 $10^5$ 个通道下发任务。

当用户输入 $-1$ 时，分配没有任务且编号最小的通道给用户。当用户输入有效的通道编号时，回收并清空此通道。

请你计算出若干次操作后，下一次用户申请时将得到的通道编号，若无可以使用的通道，返回 $-1$。

输入格式

第一行为一个整数 $n$，表示用户输入次数。

接下来一行 $n$ 个整数，分别表示每一次操作用户的输入数，通道编号在 $0$ 到 $50000$ 内。

$1 \le n \le 10^5$

输出格式

输出下一次将申请到的通道编号，若无可使用的通道，输出 $-1$。

7
-1 -1 1 -1 0 -1 2

2