在线评测链接:P1230 (opens new window)
# 注意：
100ms，基本就意味着除cpp以外，其他语言不太能通过了。
--------------------4-27更新----------------
根据群友消息，由于本场题目确实太难，相较通过率太低，所以华子HR决定这次没过的可以重考，参加下次的5.6的笔试!
# 题目内容
你是一名网络工程师，你正在为一家云计算公司开发一个虚拟机管理系统。你的系统需要为每个虚拟机分配一个唯一的ID，用来标识和通信。为了实现这个功能，你设计了一个管理ID的资源池，可以从资源池中分配资源ID和释放资源ID，分配方式有动态分配和指定分配。
动态分配是从资源池的开始分配一个资源ID，这种方式适用于新创建的虚拟机。指定分配是指定一个资源ID进行分配，这种方式适用于恢复或迁移的虚拟机。无论哪种分配方式释放资源ID时都需要放到资源池的尾部，这样可以保证资源ID的重用和均衡。
现在，你已经执行了一系列操作，你需要知道资源池的第一个空闲资源ID应该是多少，以便为下一个虚拟机分配。
注意：
资源池的初始顺序是从小到大。
资源池中空闲资源ID不足时，动态分配失败，对资源池不进行任何操作。指定分配资源ID已经被占用或者不在资源池范围内时，对资源池不进行任何操作。
释放资源ID不在资源池范围内时或者已经是空闲资源ID时，对资源池不进行任何操作。
保证每个用例最后都有空闲资源ID。
# 输入描述
输入第一行为两个整数 和 ，表示资源池的范围;
输入第二行为一个整数 ，表示操作个数。
第三行开始，第一个数字代表操作类型 ， 表示动态分配， 表示指定分配， 表示释放；
如果输入的第一个数字是 ，第二个表示分配的个数 ；
如果输入的第一个数字是 ，第二个表示分配的资源ID；
如果输入的第一个数字是 ，第二个表示释放的资源ID。
， ；
， 。
# 输出描述
资源池的第一个空闲资源ID。
# 样例
# 样例一
输入
1 3
2
1 1
3 1
输出
2
样例解释
第一行资源池范围是 ，资源池的初始顺序是 。
第二行操作个数有 个。
第三行动态分配 个资源ID，资源池中剩余的资源ID顺序是 。
第四行释放 个资源ID、资源ID是 ，资源池中剩余的资源ID顺序是 。
执行以上操作后，资源池的第一个空闲资源ID是 。
# 样例二
输入
1 3
3
2 2
3 2
1 1
输出
3
样例解释
第一行资源池范围是 ，资源池的初始顺序是 。
第二行操作个数有 个。
第三行指定分配 个资源ID，资源ID是 ，资源池中剩余的资源ID顺序是 。
第四行释放 个资源ID，资源ID是 ，资源池中剩余的资源ID顺序是 。
第五行动态分配 个资源ID，分配的资源ID是 ，资源池中剩余的资源D顺序是 。
执行以上操作后，资源池的第一个空闲资源ID是 。
# 思路：数组模拟双向链表
给定位置 ， 我们要快速维护三种操作:
1.占用 从左到右数 前个位置
2.占用指定位置
3.取消占用某位置
对于后两个操作，显然直接用一个数组可以模拟实现。而对于第一个操作，我们可以使用链表来维护未被占用的点。这样的单次操作复杂度可以达到。
引入链表后，带来新的问题:对于后两个操作，我们也需要同时删除/插入一个节点。单纯用链表是无法快速做到这一点的。
解决方法:直接使用数组来模拟链表，具体实现见代码。
注意:华为OJ只给了100ms。这意味着你需要在极低的常数下通过这题。所以只有C/C++可能过这题。而且不仅需要使用C/C++，也不允许使用STL中的List，而是需要手写链表 。 这直接导致了本场成为华为春招最难的一场，通过率极低，估计只有10%。
# 类似题目推荐
一道普通的模拟题。推荐几道模拟的真题吧
# CodeFun2000
P1030 华为od-2022.11.27-平均像素值 (opens new window)
P1026 华为秋招-2022.11.2-检测热点字符 (opens new window)
P1250 华为春招-2023.05.06-春招-第二题-加法 (opens new window)
# 代码
# C++
AC
#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;
}
← 第1题-引擎模块初始化 第3题-MC方块 →