题目描述与示例
题目描述
游乐场里增加了一批摇摇车,非常受小朋友欢迎,但是每辆摇摇车同时只能有一个小朋友使用,如果没有空余的摇摇车需要排队等候,或者直接离开,最后没有玩上的小朋友会非常不开心。
请根据今天小朋友的来去情况,统计不开心的小朋友数量。
- 摇摇车数量为
N
,范围是:1 <= N < 10
; - 每个小朋友都对应一个编码,编码是不重复的数字,今天小朋友的来去情况,可以使用编码表示为:
1 1 2 3 2 3
。(若小朋友离去之前有空闲的摇摇车,则代表玩耍后离开;不考虑小朋友多次玩的情况)。小朋友数量≤ 100
- 题目保证所有输入数据无异常且范围满足上述说明
输入描述
第一行: 摇摇车数量
第二行: 小朋友来去情况
输出描述
返回不开心的小朋友数量
示例一
输入
1
1 2 1 2
输出
0
说明
第一行,1个摇摇车 第二行,1号来 2号来(排队) 1号走 2号走(1号走后摇摇车已有空闲,所以玩后离开)
示例二
输入
1
1 2 2 3 1 3
输出
1
说明
第一行,1个摇摇车 第二行,1号来 2号来(排队) 2号走(不开心离开) 3号来(排队)1号走 3号走(1号走后摇摇车已有空闲,所以玩后离)
解题思路
在摇摇车满位的情况下,小朋友的排队顺序天然地符合先进先出的顺序,很容易想到用队列维护排队过程。
wait_queue = deque()
但本题的难点在于处理好每一个小朋友的状态。每一个小朋友均有三种不同的状态:
- 是否出现过
- 是否玩上了摇摇车
- 是否离开(无论是玩完离开还是生气离开)
因此可以用哈希表记录每一个小朋友的状态,哈希表的默认值为一个长度为3
的列表,分别对应上述的三种状态。
children_state_dic = defaultdict(lambda: [False, False, False])
遍历小朋友来去情况的序列。每一个小朋友,一共存在以下四种情况:
- 小朋友第一次出现(来到),摇摇车有位置。
- 标记小朋友已经来过
- 小朋友直接去玩
- 正在玩摇摇车的人数+1
- 注意:此时排队队列一定为空,否则摇摇车不可能有位置
- 小朋友第一次出现(来到),摇摇车没位置
- 标记小朋友已经来过
- 小朋友加入队列末尾
- 小朋友第二次出现(离开),刚刚玩上了摇摇车(满意离开)
- 标记小朋友已经离开
- 正在玩摇摇车的人数-1
- 由于玩摇摇车的人数减少,排在队头的小朋友(如果他刚刚没有生气离开),则可以出队去玩摇摇车
- 小朋友第二次出现(离开),刚刚没玩上摇摇车(生气离开)
- 标记小朋友已经离开
- 不开心的小朋友人数+1
上述分类讨论组织成代码即为
for child in children:
if children_state_dic[child][0] is False:
children_state_dic[child][0] = True
if play_num < n:
children_state_dic[child][1] = True
play_num += 1
else:
wait_queue.append(child)
else:
children_state_dic[child][2] = True
if children_state_dic[child][1] is True:
play_num -= 1
while len(wait_queue) > 0 and play_num < n:
nxt_child = wait_queue.popleft()
if children_state_dic[nxt_child][2] is False:
children_state_dic[nxt_child][1] = True
play_num += 1
else:
angry_num += 1
代码
Python
# 题目:【队列】2023B-不开心的小朋友
# 分值:200
# 作者:闭着眼睛学数理化
# 算法:队列
# 代码看不懂的地方,请直接在群上提问
from collections import deque, defaultdict
# 摇摇车数量
n = int(input())
# 小朋友序列,编码用字符串即可
children = input().split()
# 初始化小朋友的等待队列
wait_queue = deque()
# 用一个哈希表记录每一个小朋友的状态,默认值为一个长度为3的列表
# 分别表示:是否之前出现过/是否玩上了摇摇车/是否已经离开
children_state_dic = defaultdict(lambda: [False, False, False])
play_num = 0
angry_num = 0
# 遍历小朋友序列
for child in children:
# 小朋友编号第一次出现,过来玩摇摇车
if children_state_dic[child][0] is False:
# 将小朋友标记为已经来过
children_state_dic[child][0] = True
# 第一种情况:摇摇车有位置,可以玩,不用排队
if play_num < n:
children_state_dic[child][1] = True
play_num += 1
# 第二种情况:摇摇车没位置,不可以玩,加入队列排队
else:
wait_queue.append(child)
# 小朋友编号第二次出现,玩完/生气离开
else:
# 将小朋友标记为已经离开
children_state_dic[child][2] = True
# 第三种情况:这个小朋友刚刚玩上了摇摇车,现在玩完摇摇车离开
if children_state_dic[child][1] is True:
# 玩摇摇车人数-1
play_num -= 1
# 队列中正在排队的小朋友可以进来玩
while len(wait_queue) > 0 and play_num < n:
# 队头等待的小朋友nxt_child出队
nxt_child = wait_queue.popleft()
# 如果在等待队列中的小朋友,没有被标记为生气离开,则可以玩摇摇车
if children_state_dic[nxt_child][2] is False:
children_state_dic[nxt_child][1] = True
# 玩摇摇车人数+1
play_num += 1
# 第四种情况:这个小朋友刚刚没玩上摇摇车,生气离开
else:
# 生气人数+1
angry_num += 1
print(angry_num)
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
String[] children = scanner.nextLine().split(" ");
Queue<String> waitQueue = new LinkedList<>();
Map<String, List<Boolean>> childrenState = new HashMap<>();
int playNum = 0;
int angryNum = 0;
for (String child : children) {
if (!childrenState.containsKey(child)) {
childrenState.put(child, Arrays.asList(false, false, false));
}
if (!childrenState.get(child).get(0)) {
childrenState.get(child).set(0, true);
if (playNum < n) {
childrenState.get(child).set(1, true);
playNum++;
} else {
waitQueue.add(child);
}
} else {
childrenState.get(child).set(2, true);
if (childrenState.get(child).get(1)) {
playNum--;
while (!waitQueue.isEmpty() && playNum < n) {
String nxtChild = waitQueue.poll();
if (!childrenState.get(nxtChild).get(2)) {
childrenState.get(nxtChild).set(1, true);
playNum++;
}
}
} else {
angryNum++;
}
}
}
System.out.println(angryNum);
}
}
C++
“`C++
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {
int n;
cin >> n;
string child;
queue<string> waitQueue;
unordered_map<string, vector<bool>> childrenState;
int playNum = 0;
int angryNum = 0;
<pre><code>while (cin >> child) {
if (childrenState.find(child) == childrenState.end()) {
childrenState[child] = {false, false, false};
}
if (!childrenState[child][0]) {
childrenState[child][0] = true;
if (playNum < n) {
childrenState[child][1] = true;
playNum++;
} else {
waitQueue.push(child);
}
} else {
childrenState[child][2] = true;
if (childrenState[child][1]) {
playNum–;
while (!waitQueue.empty() && playNum < n) {
string nxtChild = waitQueue.front();
waitQueue.pop();
if (!childrenState[nxtChild][2]) {
childrenState[nxtChild][1] = true;
playNum++;
}
}
} else {
angryNum++;
}
}
}
cout << angryNum << endl;
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度:O(M)
。遍历每一个小朋友的情况,每一个小朋友最多出入队一次。
空间复杂度:O(M)
。哈希表和队列所占空间均为O(M)
。
说明
华为OD机试有三道题⽬,第⼀道和第⼆道属于简单或中等题,分值为 100 分,第三道为中等或困难题,分值为 200分,总分为 400 分。
机试分数越⾼评级越⾼,⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章:华为OD机考须知
关于机考题目汇总可以看这篇文章:华为OD机试真题 2023 A+B+C+D卷 + 2024新卷(Python&Java&C++)⽬录汇总(每⽇更新)