华为OD机试 不开心的小朋友

题目描述:

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

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没玩

扫描数组的时候要判断状态：第一次出现or第二次出现？

若第一次出现会有两种可能：有座->去玩；没座->排队

若第二次出现也是两种可能：哈希表对应值为1->之前玩了准备离开；值为0->排队后不开心地离开了

做的时候试了下100%通过直接就提交了 回看发现第二个用例不对

找到原因：需要再增加一个队列 以及while()：座位不满且队列非空时自动出队入座

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

int main() {
	vector<int>v;//存放小朋友先后顺序
	map<int, int>q;//哈希表 存放小朋友状态
	int l = 0;
	cin >> l;
	int tp = 0, mx = 0;
	while (cin >> tp){
		v.push_back(tp);
		if (cin.get() == '\n')
			break;
	}
	int m = l;//m用于记录空位
	for (int i = 0; i < v.size(); i++) {
		if (q.find(v[i]) == q.end()){ //哈希表中找不到该小朋友编号
			if (m > 0) {//有空位置
				q[v[i]] = 1;//小朋友开玩
				m--;
			}
			else if (m <= 0) {//无空位置
				q[v[i]] = 0;//小朋友在排队
			}
		}
		else if (q.find(v[i]) != q.end()) {//哈希表中能找到改小朋友编号 说明之前小朋友排过队了
			if (q[v[i]] == 0) {//为0说明小朋友没玩并且不开心地离开了
				mx++;
			}
			else if (q[v[i]] == 1) {//为1说明正在玩 并准备离开
				q[v[i]] = 0;//
				m++;
			}
		}
	}
	cout << mx;
}