Codeforces Round #Pi (Div. 2) B. Berland National Library

原题:http://codeforces.com/contest/567/problem/B

---

题目大意: 一个计数器, +号代表一个人进入图书馆, -号代表一个人出去图书馆. 给一个log, 问这个log中能知道的这个图书馆最小的可能容量是多少, log是片段, 在program运行前可能图书馆已经有人, 在运行后也可能人还没出去?

---

分析: 因为log不能完全记录图书馆的信息, 有可能第一条就是-号,所以我们需要用个数组记录一下人来往的信息. 但是当发现有人出去但是没有进入的信息, 我们就知道在当前时候, 图书馆的容量应该比记录的容量多1. 换句话说, 当发现一个人走出来但是没有被记录进去, 我们只能认为这个人一直在图书馆里.

   public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        boolean[] t = new boolean[1000010];
        int cap = 0;
        int cur = 0;
        for (int i = 0; i < n; i++) {
            String s = in.readLine();
            String[] ar = s.split(" ");
            if (ar[0].charAt(0) == '+' && !t[Integer.valueOf(ar[1])]) {
                cur++;
                t[Integer.valueOf(ar[1])] = true;
            }
            else if (ar[0].charAt(0) == '-' && t[Integer.valueOf(ar[1])]) {
                cur--;
                t[Integer.valueOf(ar[1])] = false;
            }
            else if (ar[0].charAt(0) == '-' && !t[Integer.valueOf(ar[1])])
                cap++;
            cap = Math.max(cap,cur);
        }
        out.print(cap);
    }