不开心的小朋友-200分

问题描述

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

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

输入格式

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

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

输出格式

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

样例输入1

1
1 2 1 2

样例输出1

0

样例输入2

1
1 2 2 3 1 3

样例输出2

1

样例解释

样例 解释说明
样例1 1号来->2号来(排队)->1号走->2号上车玩->2号走,所有小朋友都玩到了
样例2 1号来->2号来(排队)->2号不开心离开->3号来(排队)->1号走->3号上车玩->3号走,2号没玩到

数据范围

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

题解

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

  1. 实现思路
  • 使用集合记录正在玩摇摇车的小朋友
  • 使用队列记录正在排队的小朋友
  • 遍历序列模拟整个过程
  1. 关键处理
  • 当遇到已在玩的小朋友编号时,表示该小朋友玩完离开
  • 当有小朋友离开时,需要让排队的小朋友上车
  • 当遇到正在排队的小朋友编号时,表示该小朋友不开心离开
  1. 状态转移
  • 新来的小朋友:
    • 如果有空车直接玩
    • 否则去排队
  • 已在玩的小朋友:
    • 离开并让排队的上车
  • 正在排队的小朋友:
    • 不开心离开并计数

时间复杂度:,其中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;
        
        // 遍历每个小朋友
  

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

算法刷题笔记 文章被收录于专栏

本专栏收集并整理了一些刷题笔记

全部评论

相关推荐

评论
1
1
分享

创作者周榜

更多
牛客网
牛客企业服务