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}