cf #314 B. Berland National Library (模拟)

给出一个图书馆人员进出情况,问图书馆满足题意的最小容量是多少。

注意在初始之前图书馆里面可能就有人了,也就是说不是所有进入图书馆的人都会被给出。

我的做法是先统计出图书馆里面初始的人数,开一个布尔数组,初始全为false,如果一个人标记为 false  而且从 图书馆里出来了,就说明这个人初始是在图书馆里的。

然后就正常模拟,图书馆的人数由初始的和后来的两部分组成。

/*************************************************************************
	> File Name: code/cf/#314/B.cpp
	> Author: 111qqz
	> Email: rkz2013@126.com 
	> Created Time: 2015年08月06日 星期四 00时23分26秒
 ************************************************************************/
 1#include<iostream>
 2#include<iomanip>
 3#include<cstdio>
 4#include<algorithm>
 5#include<cmath>
 6#include<cstring>
 7#include<string>
 8#include<map>
 9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)  
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=1E2+5;moni
25int n;
26int r[N];
27bool vis[1000060];
28char ch[N];
29int main()
30{
31    cin>>n;
32    char cmd;
33    int mx = -1;
34    int cur = 0;
35    int beforein = 0;
36    memset(vis,false,sizeof(vis));
37    for ( int i = 0 ; i < n ; i++)
38    {
 1	cin>>ch[i]>>r[i];
 2	if (ch[i]=='+')
 3	{
 4	    vis[r[i]] = true;
 5	}
 6	if (ch[i]=='-')
 7	{
 8	    if (!vis[r[i]])
 9	    {
10		beforein++;
11	    }
12	    vis[r[i]] = false;
13	}
14    }
15    mx = beforein;
16    memset(vis,false,sizeof(vis));
17   // cout<<"beforein:"<<beforein<<endl;
18    for ( int i = 0 ; i <n ; i++ )
19    {
20	if (ch[i]=='+')
21	{
22	    cur++;
23	    vis [r[i]] =true;
24	}
25	else
26	{
27	    if (vis[r[i]])
28	    {
29//	    if (vis[1]) cout<<"fuffffffffff"<<endl;
30		cur--;
31//		cout<<"r[i]:"<<r[i]<<endl;
32		vis[r[i]] = false;
33	    }
34	    else
35	    {
36		beforein--;
37	    }
38	}
39//	cout<<"cur:"<<cur<<" beforein:"<<beforein<<endl;   
40	if (cur+beforein>mx)
41	{
42	    mx = cur + beforein;
43	}
1    }
2    cout<<mx<<endl;
3	return 0;
4}