题目描述与示例

题目描述

游乐场里增加了一批摇摇车,非常受小朋友欢迎,但是每辆摇摇车同时只能有一个小朋友使用,如果没有空余的摇摇车需要排队等候,或者直接离开,最后没有玩上的小朋友会非常不开心。

请根据今天小朋友的来去情况,统计不开心的小朋友数量。

  1. 摇摇车数量为N,范围是: 1 <= N < 10;
  2. 每个小朋友都对应一个编码,编码是不重复的数字,今天小朋友的来去情况,可以使用编码表示为:1 1 2 3 2 3。(若小朋友离去之前有空闲的摇摇车,则代表玩耍后离开;不考虑小朋友多次玩的情况)。小朋友数量≤ 100
  3. 题目保证所有输入数据无异常且范围满足上述说明

输入描述

第一行: 摇摇车数量

第二行: 小朋友来去情况

输出描述

返回不开心的小朋友数量

示例一

输入

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. 标记小朋友已经来过
    2. 小朋友直接去玩
    3. 正在玩摇摇车的人数+1
    4. 注意:此时排队队列一定为空,否则摇摇车不可能有位置
  2. 小朋友第一次出现(来到),摇摇车没位置
    1. 标记小朋友已经来过
    2. 小朋友加入队列末尾
  3. 小朋友第二次出现(离开),刚刚玩上了摇摇车(满意离开)
    1. 标记小朋友已经离开
    2. 正在玩摇摇车的人数-1
    3. 由于玩摇摇车的人数减少,排在队头的小朋友(如果他刚刚没有生气离开),则可以出队去玩摇摇车
  4. 小朋友第二次出现(离开),刚刚没玩上摇摇车(生气离开)
    1. 标记小朋友已经离开
    2. 不开心的小朋友人数+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++)⽬录汇总(每⽇更新)

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。