解题思路

系统的“驶出”记录一定正确；“驶入”记录可能缺失或重复。为使容量最小，我们可以尽量忽略所有“+”记录（把它们当成可能的噪声），只在必须时假想有一次“未被记录的驶入”。核心结论与做法如下：

1. 预处理每辆车的首次出现符号 对每个编号 $x$，找到它在序列中第一次出现是“+x”还是“-x”。

   • 若首现为“-x”，说明在系统开始记录时，这辆车就已经在场内（或更早入场）。
   • 若首现为“+x”，则它初始不在场内，之后的任何一次“-x”都意味着它在某个时刻（可能未被记录）入场过。

2. 初始在场车辆数 记 init 为首现为“-”的车的数量。开机时刻的在场数至少为 init，这是一个容量下界。

3. 线性扫描只处理“驶出” 维护当前在场数 cur 与答案 ans（容量最小值，取扫描过程的峰值）。

   • 初始：cur = init，ans = cur。

   • 扫描每个事件：

     • 若是“+x”：为降低容量，可以视作噪声，直接忽略。

     • 若是“-x”：

       • 如果这是该车第一次出现并且其首现就是“-”：这代表它本就在场，现在离开，执行 cur -= 1。
       • 其他情况（包括该车首现为“+”，或该车已经离开过一次再次离开）：这次离开前必须有一次（可能未被记录的）再次入场。为了使容量最小，我们把这次真实入场放在“刚要离开”的最晚时刻，于是此刻在场数会瞬时变为 cur + 1 再马上离开回到 cur，更新 ans = max(ans, cur + 1)，cur 不变。

   • 全程只在“首次且首现为‘-’的离开”时 cur--，其它离开只会造成一次瞬时峰值 cur+1。

4. 答案 最终 ans 即为最小可能容量。

   • 直观理解：init 是“开机瞬间”的人数峰值；
   • 而每次“无在场记录的离开”会在离开前强制出现一次“隐形入场”，把瞬时峰值抬到 cur+1。
   • 取整个过程中所有这些峰值的最大值即可。

相关算法：线性扫描 + 哈希/数组状态记录。仅需记录每车的首现符号与是否已出现过离开一次，整体 $O(n)$。

复杂度分析

• 时间复杂度：对每组数据两次线性扫描（预处理首现 & 主扫描），总计 $O(n)$。
• 空间复杂度：记录每个编号的首现符号与是否已离开过一次，数组大小为 $m$（车辆最大编号），因此 $O(m)$。
• 在约束 $n, m \le 10^5$ 下完全可行。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意实现函数与主函数分离；输入中正号优先用 literal_eval 解析
import sys
from ast import literal_eval

def min_capacity_one_case(n, m, arr):
    # first_sign[x]: 0=未出现, 1=首现为'+', -1=首现为'-'
    first_sign = [0] * (m + 1)
    # exited_once[x]: 是否已经见过一次“-x”
    exited_once = [False] * (m + 1)

    # 预处理：记录每个车的首次出现符号
    for v in arr:
        x = abs(v)
        if first_sign[x] == 0:
            first_sign[x] = 1 if v > 0 else -1

    # 初始在场数 = 首现为 '-' 的车辆数量
    init = sum(1 for x in range(1, m + 1) if first_sign[x] == -1)

    cur = init  # 当前在场数
    ans = cur   # 记录过程中的最大在场数（容量）

    # 主扫描：忽略所有 '+'，只处理 '-'
    for v in arr:
        if v > 0:
            # '+' 直接忽略（可视为重复或噪声）
            continue
        x = -v  # 离开的车牌
        if not exited_once[x]:
            # 第一次离开
            exited_once[x] = True
            if first_sign[x] == -1:
                # 首现为 '-' ：它本就在场，现在离开
                cur -= 1
            else:
                # 首现为 '+' ：必须在离开前发生一次（可能缺失的）入场
                # 该入场放到最晚时刻：瞬时人数变为 cur+1
                if ans < cur + 1:
                    ans = cur + 1
            # 处理完毕
        else:
            # 再次离开：必然又有一次（可能缺失的）入场刚发生
            if ans < cur + 1:
                ans = cur + 1
            # cur 不变（+1 后立刻 -1）
    return ans

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    T = int(next(it))
    out_lines = []
    for _ in range(T):
        n = int(next(it)); m = int(next(it))
        arr = []
        # 读取 n 个形如 "+4" 或 "-8" 的记号，优先使用 literal_eval
        for _ in range(n):
            token = next(it)
            # literal_eval 能正确解析带正负号的整数字面量
            v = literal_eval(token)
            arr.append(int(v))
        out_lines.append(str(min_capacity_one_case(n, m, arr)))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名为 Main。读取字符串，手动处理前导 '+'。
import java.io.*;
import java.util.*;

public class Main {
    // 求解单组数据的函数
    static int solveOneCase(int n, int m, int[] a) {
        int[] firstSign = new int[m + 1]; // 0:未出现, 1:'+', -1:'-'
        boolean[] exitedOnce = new boolean[m + 1];

        // 预处理首现符号
        for (int v : a) {
            int x = Math.abs(v);
            if (firstSign[x] == 0) firstSign[x] = (v > 0) ? 1 : -1;
        }

        int init = 0;
        for (int x = 1; x <= m; x++) if (firstSign[x] == -1) init++;

        int cur = init;
        int ans = cur;

        for (int v : a) {
            if (v > 0) {
                // 忽略 '+'
                continue;
            }
            int x = -v;
            if (!exitedOnce[x]) {
                exitedOnce[x] = true;
                if (firstSign[x] == -1) {
                    // 首现为 '-'：本就在场，现在离开
                    cur -= 1;
                } else {
                    // 首现为 '+'：离开前必须有一次未记录入场，瞬时峰值 cur+1
                    if (ans < cur + 1) ans = cur + 1;
                }
            } else {
                // 再次离开：同样产生一次瞬时峰值
                if (ans < cur + 1) ans = cur + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        // 默认输入方式即可（数据范围适中）
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();

        for (int tc = 0; tc < T; tc++) {
            // 读取 n, m
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            // 读取 n 个带符号的整数（形如 +4 / -8）
            st = new StringTokenizer(br.readLine());
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                String tok = st.nextToken();
                // 替换前导 '+'（若有）
                if (tok.charAt(0) == '+') tok = tok.substring(1);
                a[i] = Integer.parseInt(tok);
            }

            int ans = solveOneCase(n, m, a);
            sb.append(ans).append('\n');
        }

        System.out.print(sb.toString());
    }
}

C++

// ACM 风格主程序；读取字符串，若首字符为'+'则去掉再转为整数
#include <bits/stdc++.h>
using namespace std;

// 处理一组数据的函数
int solveOneCase(int n, int m, const vector<int>& a) {
    vector<int> firstSign(m + 1, 0);    // 0:未出现, 1:'+', -1:'-'
    vector<char> exitedOnce(m + 1, 0);  // 是否见过一次离开

    // 预处理首现符号
    for (int v : a) {
        int x = abs(v);
        if (firstSign[x] == 0) firstSign[x] = (v > 0) ? 1 : -1;
    }

    int init = 0;
    for (int x = 1; x <= m; ++x) if (firstSign[x] == -1) ++init;

    int cur = init;
    int ans = cur;

    for (int v : a) {
        if (v > 0) {
            // 忽略 '+'
            continue;
        }
        int x = -v;
        if (!exitedOnce[x]) {
            exitedOnce[x] = 1;
            if (firstSign[x] == -1) {
                // 首现为 '-' ：本就在场 -> 此刻离开
                --cur;
            } else {
                // 首现为 '+' ：离开前必须有一次未记录入场，瞬时峰值 cur+1
                ans = max(ans, cur + 1);
            }
        } else {
            // 再次离开：同理会出现瞬时峰值
            ans = max(ans, cur + 1);
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            string tok; 
            cin >> tok;
            // 若有前导 '+'，去掉再解析
            if (!tok.empty() && tok[0] == '+') tok = tok.substr(1);
            a[i] = stoi(tok);
        }
        cout << solveOneCase(n, m, a) << "\n";
    }
    return 0;
}

题目内容

小明的公司停车场最近引入了一个车辆记录系统。当有一个编号为 $i$ 的车驶入时，系统会报告 $(+i)$ 。当编号为 $j$ 的车驶出时，系统会报告 $(-j)$ 。这个系统在某个时刻启动了，并一直记录了连续的一段时间的车辆情况。很遗憾的是，该系统有漏洞，可能会重复或缺失车辆进入的信息，但是车辆驶出的信息绝不会出现错误。现在小明想要通过这份系统的报告来推测，这个停车场的最小容量是多少辆车。注意当停车场满的时候没有车能够驶入。

输入描述

第一行 $1$ 个整数 $T$ ，表示数据组数。对每组数据：

第一行两个整数 $n$ 和 $m$ ，表示小明从系统中读到的报告总数，和车辆编号最大值。

第二行 $n$ 个整数， $a_1, a_2, ..., a_n$ ，依次表示从最久远到最近的报告。其中正数前会有 $(+)$，表示车辆驶入，负数表示车辆驶出，含义于题面一致。

$1 ≤ t ≤ 5; 1 ≤ n, m ≤ 100000; 1 ≤ |a_i| ≤ m$

输出描述

对于每组数据，输出一行一个数表示答案。

样例1

输入

3
3 100
+4 -100 -8
3 1000
-1 +1 -1
3 10
+1 -1 +2

输出

2
1
1

说明

对于第一组样例，完整的记录可能为 $(+4$ $+100$ $-100$ $+8$ $-8)$，因此最小容量可以推测为 $2$ ；

对于第二组样例，完整的记录可能为 $(+1$ $-1$ $+1$ $-1)$，因此最小容量可以推测为 $1$ ；

对于第三组样例，完整的记录可能为 $(+1$ $-1$ $+2)$，因此最小容量可以推测为 $1$ 。