题目大意:一个图书馆入口系统,可以识别进入人的id以及离开人的id。现在一段记录‘+’表示进入,‘-’表示离开,后面跟着id。问根据这个记录,推出图书馆最少可以容纳多少人。
解题思路:初始容纳人数为0,如果在累积进入n人之前没有n个人离开图书馆,则图书馆的容纳人数要加一。如果进入累积n人之前有n个人离开,则容纳人数不加一。如果有人离开,判断离开的人是否之前进入的,如果是,说明不用额外记录,否则需要容纳人数加一。用一个变量out来记录累积离开的人,每次进入人时,如果未将累积进入的抵消,就要减少且容纳人数不增加。
ac代码:
#include <iostream>
#include <set>
using namespace std;
set <int>se;
int sum, n, num, out;
char ch;
int main()
{while (scanf("%d", &n) != EOF){sum = out = 0;for (int i=0; i<n; i++){scanf("\n%c %d", &ch, &num);if (ch == '+'){se.insert(num); if (out)out--;elsesum++; }else{if (!se.count(num))sum++; elsese.erase(num); out++;}}printf("%d\n", sum);se.clear();}
return 0;
}