刷题笔记合集🔗

不开心的小朋友

问题描述

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

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

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

输入格式

第一行：摇摇车数量
第二行：小朋友来去情况（用空格分隔的编码序列）

输出格式

输出的唯一一行包含一个整数，表示不开心的小朋友数量。

样例输入

1
1 2 1 2

1
1 2 2 3 1 3

样例输出

0

1

数据范围

• 
• 小朋友数量

题解

这个问题描述了一个摇摇车排队场景，我们需要统计最终有多少小朋友因为没玩到而不开心离开。

问题分析

当我们看到这个问题时，首先需要理解小朋友的三种可能状态：

1. 正在玩摇摇车的小朋友
2. 正在排队等待的小朋友
3. 新来的小朋友

当读取到一个小朋友编号时，我们需要判断这个编号代表什么行为：

• 如果该编号的小朋友正在玩摇摇车，则表示他玩完了，开心离开
• 如果该编号的小朋友正在排队，则表示他不想等了，不开心离开
• 如果该编号的小朋友既不在玩也不在排队，则是新来的小朋友

解题思路

我们可以用两个数据结构来跟踪小朋友的状态：

1. 一个集合(Set)记录正在玩摇摇车的小朋友编号
2. 一个队列(Queue)记录正在排队的小朋友编号

然后遍历输入的小朋友编号序列，分情况处理：

• 情况1：小朋友在摇摇车上

  • 将该小朋友从"正在玩"集合中移除
  • 如果有人在排队，让队首的小朋友上车玩

• 情况2：小朋友在排队

  • 将该小朋友从队列中移除
  • 不开心计数器+1

• 情况3：小朋友是新来的

  • 如果有空闲的摇摇车(玩的人数<N)，让他直接玩
  • 否则让他去排队

时间复杂度分析

假设小朋友总数为m，则：

• 时间复杂度：O(m²)，最坏情况下，对于每个小朋友，我们可能需要在队列中查找他的位置，这是O(m)操作
• 空间复杂度：O(m)，用于存储正在玩和正在排队的小朋友

对于本题，小朋友数量最多为100，所以这个复杂度是可以接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 输入摇摇车数量
n = int(input())
# 输入小朋友来去情况
kids = input().split()

def count_unhappy():
    # 不开心的小朋友数量
    unhappy = 0
    
    # 正在玩摇摇车的小朋友编号
    playing = set()
    # 排队等待的小朋友队列
    queue = []
    
    for kid in kids:
        # 情况1：小朋友正在玩摇摇车
        if kid in playing:
            # 小朋友玩完离开
            playing.remove(kid)
            
            # 如果有人排队，让排在第一位的人上车
            if queue:
                playing.add(queue.pop(0))
            continue
        
        # 情况2：小朋友正在排队
        if kid in queue:
            # 小朋友不开心离开
            queue.remove(kid)
            unhappy += 1
            continue
        
        # 情况3：新来的小朋友
        if len(playing) < n:
            # 有空余摇摇车，直接玩
            playing.add(kid)
        else:
            # 没有空余摇摇车，去排队