不开心的小朋友 - 华为OD统一考试

OD统一考试

题解： Java / Python / C++

题目描述

游乐场里增加了一批摇摇车，非常受小朋友欢迎，但是每辆摇摇车同时只能有一个小朋友使用如果没有空余的摇摇车，需要排队等候，或者直接离开，最后没有玩上的小朋友会非常不开心。请根据今天小朋友的来去情况，统计不开心的小朋友数量。

1、摇摇车数量为N，范围是: 1<=N<=10:

2、每个小朋友都对应一个编码，编码是不重复的数字，今天小朋友的来去情况可以使用编码表示为: 1 1 2 3 2 3。 (若小朋友离去之前有空闲的摇摇车则代表玩要后离开:不考虑小朋友多次玩的情况)。小朋友数量<=100

3、题目保证所有输入数据无异常目范围满足上述说明

输入描述

第一行: 摇摇车数量

第二行:小朋友来去情况

输出描述

返回不开心的小朋友数量

示例1

输入:
1
1 2 1 2

输出:
0

说明:
第一行，1个摇摇车
第二行，1号来 2号来(排队) 1号走 2号走(1号走后摇摇车已有空闲，所以玩后离开)

示例2

输入:
1
1 2 2 3 1 3

输出:
1

说明:
第一行，1个摇摇车
第二行，1号来 2号来 (排队) 2号走 (1号还没走，所以2号没玩3号来，1号走，3号走(1走后摇摇车有空闲，所以玩后离开)。只有2没玩

题解

模拟题

这个问题可以用队列来模拟小朋友玩摇摇车的过程。使用一个集合 playing 来记录当前正在玩摇摇车的小朋友，一个集合 unpappy 来记录因为没有玩到而不开心的小朋友，一个队列 waiting_queue 来记录排队的小朋友。

遍历输入的小朋友的来去情况，对每个小朋友进行如下操作：

1. 如果小朋友在 playing 中，代表小朋友玩了一次后离开，此时需要检查排队队列 waiting_queue 是否有小朋友在排队，有的话让其中一个小朋友去玩，然后将其从排队队列中移除。
2. 如果小朋友在 waiting_set 中，代表小朋友离开前排在摇摇车前排但是没有玩到，将其添加到 unpappy 中。
3. 如果小朋友在 playing 和 waiting_set 中都不存在，说明小朋友是第一次来摇摇车。如果当前摇摇车有空位，直接让小朋友玩，并将其添加到 playing 中；否则，将小朋友添加到排队队列 waiting_queue 和排队集合 waiting_set 中。
4. 最后输出 unpappy 集合的大小，即不开心的小朋友数量。

这个算法的时间复杂度是 O(N)，其中 N 为小朋友的数量。

Java

import java.util.*;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        Set<Integer> playing = new HashSet<>(), unpappy = new HashSet<>();
        Set<Integer> waitingSet = new HashSet<>();
        Deque<Integer> waitingQueue = new LinkedList<>();
        while (scanner.hasNext()) {
            int boy = scanner.nextInt();
            if (playing.contains(boy)) {  // 玩后离开
                playing.remove(boy);
                while (!waitingQueue.isEmpty()) {  // 检测是否有在排队，有排队则可让一个小朋友去玩
                    int nextBoy = waitingQueue.poll();
                    if (waitingSet.contains(nextBoy)) {  // 小朋友任然在排队