不开心的小朋友-200分

问题描述

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

请你帮小兰根据今天小朋友的来去情况，统计有多少个不开心的小朋友。

输入格式

第一行输入一个整数 ，表示摇摇车的数量。

第二行输入一个序列，表示小朋友的来去情况。序列中的每个数字代表一个小朋友的编号，编号出现两次分别表示该小朋友的到达和离开。

输出格式

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

样例输入1

1
1 2 1 2

样例输出1

0

样例输入2

1
1 2 2 3 1 3

样例输出2

1

样例解释

数据范围

• ，表示摇摇车数量
• 小朋友数量不超过 100
• 每个小朋友的编号互不相同
• 每个小朋友恰好出现两次，分别表示到达和离开

题解

这是一个队列模拟题，需要维护两个集合：

1. 实现思路

• 使用集合记录正在玩摇摇车的小朋友
• 使用队列记录正在排队的小朋友
• 遍历序列模拟整个过程

2. 关键处理

• 当遇到已在玩的小朋友编号时，表示该小朋友玩完离开
• 当有小朋友离开时，需要让排队的小朋友上车
• 当遇到正在排队的小朋友编号时，表示该小朋友不开心离开

3. 状态转移

• 新来的小朋友：
  • 如果有空车直接玩
  • 否则去排队
• 已在玩的小朋友：
  • 离开并让排队的上车
• 正在排队的小朋友：
  • 不开心离开并计数

时间复杂度：，其中n是序列长度。

参考代码

def solve(n, kids):
    """
    n: 摇摇车数量
    kids: 小朋友来去序列
    return: 不开心的小朋友数量
    """
    # 记录不开心的小朋友数量
    unhappy = 0
    
    # 正在玩的小朋友集合
    playing = set()
    # 正在排队的小朋友队列
    waiting = []
    
    # 遍历每个小朋友
    for kid in kids:
        # 如果小朋友正在玩
        if kid in playing:
            # 小朋友离开
            playing.remove(kid)
            # 让排队的小朋友上车
            if waiting:
                playing.add(waiting.pop(0))
            continue
            
        # 如果小朋友正在排队
        if kid in waiting:
            # 不开心离开
            unhappy += 1
            waiting.remove(kid)
            continue
            
        # 新来的小朋友
        if len(playing) < n:
            # 直接玩
            playing.add(kid)
        else:
            # 去排队
            waiting.append(kid)
            
    return unhappy

# 读取输入
n = int(input())
kids = input().split()
# 输出结果
print(solve(n, kids))

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // 处理小朋友来去情况
    int solve(int n, vector<string>& kids) {
        // 记录不开心的小朋友数量
        int sad_cnt = 0;
        
        // 正在玩的小朋友集合
        unordered_set<string> play_set;
        // 正在排队的小朋友队列
        vector<string> wait_que;
        
        // 遍历每个小朋友