不开心的小朋友 - 华为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)) {  // 小朋友任然在排队
                        playing.add(nextBoy);
                        waitingSet.remove(nextBoy);
                        break;
                    }
                }
            } else if (waitingSet.contains(boy)) {  // 不想等直接离开(不开心)
                unpappy.add(boy);
                waitingSet.remove(boy);
            } else if (playing.size() < N) {  // 有空闲的可以玩
                playing.add(boy);
            } else {   // 没有空闲，进行排队
                waitingQueue.offer(boy);
                waitingSet.add(boy);
            }
        }

        System.out.println(unpappy.size());
    }
}

控制台模拟数据结束输入使用 Ctrl +Ｄ

Python

from collections import deque


N = int(input())
q = list(map(int, input().split()))

# 正在玩的小朋友， 没玩到不开心的小朋友
playing, unpappy = set(), set()
# 排队队列，排队中的小朋友
waiting_set, waiting_queue = set(), deque()

for boy in q:
    if boy in playing:  # 玩后离开
        playing.remove(boy)
        while waiting_queue:  # 检测是否有在排队， 有排队则可让一个小朋友去玩
            next_boy = waiting_queue.popleft()
            if next_boy in waiting_set:  # 小朋友任然在排队
                playing.add(next_boy)
                waiting_set.remove(next_boy)
                break
    elif boy in waiting_set:  # 不想等直接离开(不开心)
        unpappy.add(boy)
        waiting_set.remove(boy)
    elif len(playing) < N:  # 有空闲的可以玩
        playing.add(boy)
    else:   # 没有空闲，进行排队
        waiting_queue.append(boy)
        waiting_set.add(boy)

print(len(unpappy))

C++

#include <iostream>
#include <unordered_set>
#include <deque>

using namespace std;

int main() {
    int N;
    cin >> N;

    unordered_set<int> playing, unpappy, waitingSet;
    deque<int> waitingQueue;

    int boy;
    while (cin >> boy) {
        if (playing.count(boy)) {  // 玩后离开
            playing.erase(boy);
            while (!waitingQueue.empty()) {  // 检测是否有在排队，有排队则可让一个小朋友去玩
                int nextBoy = waitingQueue.front();
                waitingQueue.pop_front();
                if (waitingSet.count(nextBoy)) {  // 小朋友任然在排队
                    playing.insert(nextBoy);
                    waitingSet.erase(nextBoy);
                    break;
                }
            }
        } else if (waitingSet.count(boy)) {  // 不想等直接离开(不开心)
            unpappy.insert(boy);
            waitingSet.erase(boy);
        } else if (playing.size() < N) {  // 有空闲的可以玩
            playing.insert(boy);
        } else {   // 没有空闲，进行排队
            waitingQueue.push_back(boy);
            waitingSet.insert(boy);
        }
    }

    cout << unpappy.size() << endl;

    return 0;
}

CodeBlocks 控制台结束输入使用 Ctrl + C

🙏整理题解不易， 如果有帮助到您，请给点个赞 ???? 和收藏 ?，让更多的人看到。🙏🙏🙏