不开心的小朋友-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
- 每个小朋友的编号互不相同
- 每个小朋友恰好出现两次,分别表示到达和离开
题解
这是一个队列模拟题,需要维护两个集合:
- 实现思路
- 使用集合记录正在玩摇摇车的小朋友
- 使用队列记录正在排队的小朋友
- 遍历序列模拟整个过程
- 关键处理
- 当遇到已在玩的小朋友编号时,表示该小朋友玩完离开
- 当有小朋友离开时,需要让排队的小朋友上车
- 当遇到正在排队的小朋友编号时,表示该小朋友不开心离开
- 状态转移
- 新来的小朋友:
- 如果有空车直接玩
- 否则去排队
- 已在玩的小朋友:
- 离开并让排队的上车
- 正在排队的小朋友:
- 不开心离开并计数
时间复杂度:,其中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%内容,订阅专栏后可继续查看/也可单篇购买
算法刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记