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

本文主要是介绍不开心的小朋友 - 华为OD统一考试，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OD统一考试

题解： Java / Python / C++

alt

题目描述

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

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 来记录排队的小朋友。

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

如果小朋友在 playing 中，代表小朋友玩了一次后离开，此时需要检查排队队列 waiting_queue 是否有小朋友在排队，有的话让其中一个小朋友去玩，然后将其从排队队列中移除。
如果小朋友在 waiting_set 中，代表小朋友离开前排在摇摇车前排但是没有玩到，将其添加到 unpappy 中。
如果小朋友在 playing 和 waiting_set 中都不存在，说明小朋友是第一次来摇摇车。如果当前摇摇车有空位，直接让小朋友玩，并将其添加到 playing 中；否则，将小朋友添加到排队队列 waiting_queue 和排队集合 waiting_set 中。
最后输出 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 dequeN = 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)breakelif 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;
}