ID: 14

Difficulty: 9

注意：

100ms，基本就意味着除cpp以外，其他语言不太能通过了。

--------------------4-27更新----------------

根据群友消息，由于本场题目确实太难，相较通过率太低，所以华子HR决定这次没过的可以重考，参加下次的5.6的笔试!

题目内容

你是一名网络工程师，你正在为一家云计算公司开发一个虚拟机管理系统。你的系统需要为每个虚拟机分配一个唯一的ID，用来标识和通信。为了实现这个功能，你设计了一个管理ID的资源池，可以从资源池中分配资源ID和释放资源ID，分配方式有动态分配和指定分配。

动态分配是从资源池的开始分配一个资源ID，这种方式适用于新创建的虚拟机。指定分配是指定一个资源ID进行分配，这种方式适用于恢复或迁移的虚拟机。无论哪种分配方式释放资源ID时都需要放到资源池的尾部，这样可以保证资源ID的重用和均衡。

现在，你已经执行了一系列操作，你需要知道资源池的第一个空闲资源ID应该是多少，以便为下一个虚拟机分配。

注意：

资源池的初始顺序是从小到大。

资源池中空闲资源ID不足时，动态分配失败，对资源池不进行任何操作。指定分配资源ID已经被占用或者不在资源池范围内时，对资源池不进行任何操作。

释放资源ID不在资源池范围内时或者已经是空闲资源ID时，对资源池不进行任何操作。

保证每个用例最后都有空闲资源ID。

输入描述

输入第一行为两个整数 $l$ 和 $r$ ，表示资源池的范围;

输入第二行为一个整数 $t$ ，表示操作个数。

第三行开始，第一个数字代表操作类型 $op$ ， $1$ 表示动态分配， $2$ 表示指定分配， $3$ 表示释放；

如果输入的第一个数字是 $1$ ，第二个表示分配的个数 $num$ ；

如果输入的第一个数字是 $2$ ，第二个表示分配的资源ID；

如果输入的第一个数字是 $3$ ，第二个表示释放的资源ID。

$1\le l\lt r \le 100000$ ， $1\le t \le 100000$ ；

$1\le op \le 3$ ， $1\le num\le 200$ 。

输出描述

资源池的第一个空闲资源ID。

样例

样例一

输入

输出

样例解释

第一行资源池范围是 $[1,3]$ ，资源池的初始顺序是 $1->2->3$ 。

第二行操作个数有 $2$ 个。

第三行动态分配 $1$ 个资源ID，资源池中剩余的资源ID顺序是 $2->3$ 。

第四行释放 $1$ 个资源ID、资源ID是 $1$ ，资源池中剩余的资源ID顺序是 $2->3->1$ 。

执行以上操作后，资源池的第一个空闲资源ID是 $2$ 。

样例二

输入

输出

样例解释

第一行资源池范围是 $[1,3]$ ，资源池的初始顺序是 $1->2->3$ 。

第二行操作个数有 $3$ 个。

第三行指定分配 $1$ 个资源ID，资源ID是 $2$ ，资源池中剩余的资源ID顺序是 $1->3->2$ 。

第四行释放 $1$ 个资源ID，资源ID是 $2$ ，资源池中剩余的资源ID顺序是 $1->3->2$ 。

第五行动态分配 $1$ 个资源ID，分配的资源ID是 $1$ ，资源池中剩余的资源D顺序是 $3->2$ 。

执行以上操作后，资源池的第一个空闲资源ID是 $3$ 。

题目描述

你是一名网络工程师，正在开发一个虚拟机管理系统，需要管理虚拟机的资源ID。为了确保每个虚拟机的ID唯一且可复用，你设计了一个资源池，支持三种操作：动态分配：从资源池中按顺序分配指定数量的资源ID，适用于新创建的虚拟机。指定分配：指定一个资源ID进行分配，适用于恢复或迁移的虚拟机。释放资源：释放已经分配的资源ID，使其可再次使用。每当资源ID被分配或释放时，资源池的管理会调整顺序，使得资源ID能够合理复用。你需要在执行操作后输出资源池的第一个空闲资源ID。

思路

数组模拟双向链表

思路步骤

1.初始化资源池： 给定资源池的范围 [l, r]，我们需要用两个数组分别表示每个资源ID的左邻居和右邻居，同时还需要一个数组表示某个资源ID是否被占用。

2.动态分配资源ID： 根据要求，动态分配会从资源池的开始位置，按顺序分配指定数量的ID。每次分配一个ID后，我们将其从可用资源链表中移除，并更新链表的头部指针。

3.指定分配资源ID： 如果指定分配的ID在资源池范围内且未被占用，则将其从可用链表中移除。如果该ID正好是资源池的头或尾，还需要特别处理。

4.释放资源ID： 释放的资源ID需要重新加入到资源池的尾部，同时恢复它与前后节点的连接。

5.操作执行后： 每次操作结束后，输出资源池中第一个空闲的资源ID。

引入链表后，带来新的问题:对于后两个操作，我们也需要同时删除/插入一个节点。单纯用链表是无法快速做到这一点的。

解决方法:直接使用数组 $c$ 来模拟链表，具体实现见代码。

注意:华为OJ只给了100ms。这意味着你需要在极低的常数下通过这题。所以只有C/C++可能过这题。而且不仅需要使用C/C++，也不允许使用STL中的List，而是需要手写链表 。这直接导致了本场成为华为春招最难的一场，通过率极低，估计只有10%。

代码说明

1.初始化链表：创建两个数组 L 和 R，分别表示每个资源ID的左邻居和右邻居；另一个数组 ud 用于标记每个资源ID是否被使用。

2.动态分配：

检查是否有足够的可用资源；按顺序从链表中取出 num 个资源ID；移除这些ID，并更新链表的头部。

3.指定分配：

检查指定的资源ID是否在范围内且未被占用；将其从链表中移除，更新其前后连接。

4.释放资源ID：

检查释放的资源ID是否在范围内且已经被占用；将其加入链表的尾部，更新链表的连接关系。

5.输出结果：

输出当前链表的第一个空闲资源ID，即当前的链表头部。

代码

C++

#include <iostream>

using namespace std;

const int N = 100010;
int l, r;
int n;

// 每个节点的左节点和右节点
int L[N], R[N];
// 节点是否已经被使用
int ud[N];
// 剩余节点数量，当前起始节点，当前末尾节点
int remain, beg, ed;

int main()
{
  cin >> l >> r;
  
  // 建立“链表”关系
  for(int i=l; i<=r; i++) {
    L[i] = i-1;
    R[i] = i+1;
  }

  cin >> n;
  
  beg = l, ed = r;
  remain = r-l+1;

  for(int i=0; i<n; i++) {
    int op, v;
    cin >> op >> v;
    if(op == 1) {
      // 不够分配
      if(remain < v) continue;
      while(v--) {
        // “孤立”当前节点
        R[L[beg]] = R[beg];
        L[R[beg]] = L[beg];
        ud[beg] = 1;
        remain--;
        // 更新起始节点
        beg = R[beg];
      }
    } else if(op == 2) {
      if(v < l || v > r || ud[v]) continue;
      // “孤立”当前节点
      R[L[v]] = R[v];
      L[R[v]] = L[v];
      // 如果指定分配的节点是首尾节点，要特殊处理一下
      if(v == beg) beg = R[v];
      else if(v == ed) ed = L[v];

      ud[v] = 1;
      remain--;
    } else {
      if(v < l || v > r || !ud[v]) continue;
      if(remain == 0) {
        // 当前资源全部用完，特殊处理
        beg = ed = v;
      } else {
        // 把当前节点放到最后，建立前后关系
        R[ed] = v;
        L[v] = ed;
        ed = v;
      }
      ud[v] = 0;
      remain++;
    }
  }
  cout << beg << endl;
}
// by JAY

python

超时

class Node:
    def __init__(self, r_id=None) -> None:
        self.pre = None
        self.next = None
        self.r_id = r_id
        
dummy_head = Node() # 头部存储最近没使用过的结点
dummy_tail = Node() # 尾部存储最近刚使用过的结点
dummy_head.next = dummy_tail
dummy_tail.pre = dummy_head
    
id2node = {}

def addTail(node:Node):
    global dummy_tail
    dummy_tail.pre.next = node
    node.pre = dummy_tail.pre
    node.next = dummy_tail
    dummy_tail.pre = node

def removeNode(node:Node):
    node.pre.next = node.next
    node.next.pre = node.pre


r1, r2 = [int(item) for item in input().split()]
for r_id in range(r1, r2+1):
    node = Node(r_id)
    id2node[r_id] = node
    addTail(node)
t = int(input())

for _ in range(t):
    op = [int(item) for item in input().split()]
    # 动态删除最前面的多个
    if op[0]==1:
        delete_num = op[1]
        if delete_num>len(id2node): # 资源池中空闲资源不足时，动态分配失败，对资源池不进行任何操作。
            continue
        node = dummy_head.next
        while node is not None and node.r_id is not None and delete_num>0:
            removeNode(node)
            del id2node[node.r_id]
            delete_num-=1
            node = node.next
    # 删除指定的某个
    elif op[0]==2:
        delete_id = op[1]
        if delete_id>=r1 and delete_id<=r2 and delete_id in id2node:
            node = id2node[delete_id]
            removeNode(node)
            del id2node[node.r_id]
    # 添加一个到尾部
    elif op[0]==3:
        add_id = op[1]
        if add_id not in id2node:
            node = Node(add_id)
            addTail(node)
            id2node[add_id] = node
print(dummy_head.next.r_id)

Java

超时

import java.util.*;

public class Main {
    public void solution(){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] inDegree = new int[n + 1];
        inDegree[0] = -1;
        ArrayList<Integer>[] outDegree = new ArrayList[n + 1];
        for(int i = 1; i <= n; ++i){
            int m = scanner.nextInt();
            inDegree[i] += m;
            for(int j = 0; j < m; ++j){
                int from = scanner.nextInt();
                if(outDegree[from] == null)
                    outDegree[from] = new ArrayList<>();
                outDegree[from].add(i);
            }
        }
        scanner.close();
        int res = 0;
        boolean check;
        Queue<Integer> queue = new LinkedList<>();
        do {
            check = false;
            for(int i = 1; i < inDegree.length; ++i){
                if(inDegree[i] == 0){
                    inDegree[i] = -1;
                    check = true;
                    queue.offer(i);
                }
            }
            if(check)
                res += 1;
            while(!queue.isEmpty()){
                int from = queue.poll();
                if(outDegree[from] == null)
                    continue;
                for(int i = 0; i < outDegree[from].size(); ++i)
                    --inDegree[outDegree[from].get(i)];
            }
        }while(check);
        for(int i = 1; i < inDegree.length; ++i){
            if(inDegree[i] != -1){
                System.out.println(-1);
                return;
            }
        }
        System.out.println(res);
    }
    public static void main(String[] args) {
        Main m = new Main();
        m.solution();
    }
}

Go

能够AC，出自233大佬之手！

package main

import "io/ioutil"
import "os"


func read(buf []byte) (int, []byte) {
    for buf[0] < '0' || buf[0] > '9' {
        buf = buf[1:]
    }
    ans := 0
    for len(buf) > 0 && buf[0] >= '0' && buf[0] <= '9' {
        ans = ans * 10 + int(buf[0]) - '0'
        buf = buf[1:]
    }
    return ans, buf
}

func write(out []byte, x int) []byte {
    cnt := 0
    for x != 0 {
        out = append(out, byte(x % 10 + '0'))
        x /= 10
        cnt++
    }
    s := out[len(out) - cnt:]
    l, r := 0, cnt - 1
    for l < r {
        s[l], s[r] = s[r], s[l]
        l++
        r--
    }
    return out
}

func endl(out []byte) []byte {
    return append(out, '\n')
}

const maxn int = 3000001
var nxt, pre, val, id [maxn]int

func main() {
    buf, err := ioutil.ReadAll(os.Stdin)
    if err != nil {
        return
    }
    out := make([]byte, 0)
    
    l, buf := read(buf)
    r, buf := read(buf)
    t, buf := read(buf)
    head, curr, total := 0, 0, 0
    mem := r - l + 1
    for i := l; i <= r; i++ {
        total++
        val[total] = i
        id[i] = total
        pre[total] = curr
        nxt[curr] = total
        curr = total
    }
    total++
    tail := total
    nxt[total - 1] = tail
    pre[tail] = total - 1
    
    for i := 1; i <= t; i++ {
        var op, num int
        op, buf = read(buf)
        num, buf = read(buf)
        if op == 1 {
            if mem >= num {
                mem -= num
                for i := nxt[head]; num > 0; num-- {
                    id[val[i]] = 0
                    val[i] = 0
                    nxt[pre[i]] = nxt[i]
                    pre[nxt[i]] = pre[i]
                    nxtnode := nxt[i]
                    nxt[i], pre[i] = -1, -1
                    i = nxtnode
                }
            }
        } else if op == 2 {
            if id[num] != 0 {
                node := id[num]
                pre[nxt[node]] = pre[node]
                nxt[pre[node]] = nxt[node]
                id[num] = 0
                val[node] = 0
                nxt[node], pre[node] = -1, -1
                mem--
            }
        } else {
            if id[num] == 0 && num >= l && num <= r {
                total++
                id[num] = total
                val[total] = num
                pre[total] = pre[tail]
                nxt[pre[tail]] = total

                nxt[total] = tail
                pre[tail] = total
                mem++
            }
        }
    }
    out = write(out, val[nxt[head]])
    out = endl(out)
    os.Stdout.Write(out)
}

Js

超时...

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
// 资源池范围
let start, end;
// 操作个数
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 1) {
    [start, end] = lines[0].split(" ").map(Number);
  }

  if (lines.length == 2) {
    n = lines[1] - 0;
  }

  if (n && lines.length == n + 2) {
    // 资源池
    const link = new Set();
    for (let i = start; i <= end; i++) link.add(i);
    // 操作
    const operates = lines.slice(2).map((line) => line.split(" ").map(Number));
    console.log(getResult(start, end, link, operates));
    lines.length = 0;
  }
});

function getResult(start, end, link, operates) {
  // 操作类型,操作数
  for (let [type, val] of operates) {
    switch (type) {
      case 1:
        // 如果操作类型是1，即动态分配，那么操作数含义就是：分配次数
        // 【资源池中空闲资源ID不足时，动态分配失败，对资源池不进行任何操作】
        // while (link.size > 0 && val > 0) {
        //   const [num] = link;
        //   link.delete(num);
        //   val--;
        // }

        if (val >= link.size) link.clear();
        else {
          link = new Set([...link].slice(val));
        }

        break;
      case 2:
        // 如果操作类型是2，即指定分配，那么操作数含义就是：分配的资源ID
        // 【指定分配资源ID已经被占用或者不在资源池范围内时，对资源池不进行任何操作】
        link.delete(val);
        break;
      case 3:
        // 如果操作类型是3，即释放，那么操作数含义就是：释放的资源ID
        // 【释放资源ID不在资源池范围内时或者已经是空闲资源ID时，对资源池不进行任何操作】
        if (start <= val && val <= end) link.add(val);
        break;
    }
  }

  const [ans] = link;
  return ans;
}

#P1574. 2023.04.26-暑期实习-第二题-分配资源ID

2023.04.26-暑期实习-第二题-分配资源ID

注意：