2023.11.29-秋招-第一题-任务分配

1

ichbinbobobo LV 7 @ 6 months ago

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
    int total_operation; cin >> total_operation;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    for(int i = 0; i < total_operation; ++i)
    {
        min_heap.push(i);
    }

    for(int i = 0; i< total_operation; ++i)
    {
        int temp; cin >> temp;
        if(temp == -1 && min_heap.size() != 0)
        {
            min_heap.pop();
        }   
        else
        {
            min_heap.push(temp);
        }    
    }
    if(min_heap.size() !=0)
        cout << min_heap.top();
    return 0;
}

0

老友人来人往 LV 7 @ 5 months ago

import heapq
n = int(input())
free = list(range(100001))
heapq.heapify(free)
busy_set = set()
data = list(map(int,input().split()))
for x in data:
    if x == -1:
        if free:
            temp = heapq.heappop(free)
            busy_set.add(temp)
    else:
        if x in busy_set:
            busy_set.remove(x)
            heapq.heappush(free,x)

if free:
    while free and free[0] in busy_set:
        heapq.heappop(free)
    if free:
        print(free[0])
    else:
        print(-1)
else:
    print(-1)

0

wangxuehui LV 9 @ 6 months ago

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm> // 包含lower_bound

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> ops(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> ops[i];
    }

    deque<int> q;
    for (int i = 0; i < 50000; ++i) {
        q.push_back(i); // 初始化队列，包含0到99999的所有整数
    }

    for (int op : ops) {
        if (op == -1) {
            // 从左边弹出
            if (!q.empty()) {
                q.pop_front();
            }
        } else {
            // 使用lower_bound找到插入位置，并插入op
            auto pos = lower_bound(q.begin(), q.end(), op);
            q.insert(pos, op);
        }
    }

    if (!q.empty()) {
        cout << q.front() << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

0

wangxuehui LV 9 @ 6 months ago

不是，这个官方的c++代码也过不了啊

0

TaZi SU @ 7 months ago

题面描述

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

思路：模拟/小根堆

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

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

解决思路

初始化：
- 使用一个 set（集合）来存储所有可用的通道编号，初始化时将 $0$ 到 $100000$ 的所有编号插入集合中。由于集合会自动保持元素的有序性，集合的头元素即为当前最小的空闲通道编号。
处理用户输入：
- 当用户输入 -1 时，表示需要分配一个通道编号，我们从集合中取出并删除最小的元素。
- 当用户输入一个有效的通道编号 x 时，表示释放该通道编号，我们将其添加回集合中。
输出结果：
- 在所有操作完成后，如果集合中仍有元素，输出集合的头元素（即最小的可用通道编号）；如果集合为空，输出 -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();
    }
}

5 solutions

题面描述

思路：模拟/小根堆

解决思路

复杂度分析

时间复杂度

代码

Information

Status

Development

Support