中国电信 10 月 17 日机考笔试：仓库进出停留账与定长区间和计数

《面试题目》

1. 仓库进出停留账：按顺序给出 m 条 IN a / OUT a 记录，第 i 条记录对应的时刻为 i。物品已在库时再次 IN、或物品不在库时 OUT，该条记录不予接受。每次被接受的 OUT 会产生「当前时刻减去该物品最近一次被接受的入库时刻」的停留时长。需要输出四个量：被接受的记录条数、不予接受的记录条数、所有被接受的出库停留时长之和、流程结束时的在库物品件数。
2. 定长区间和计数：给定 m 个整数和正整数 t，考察所有由连续 t 项组成的片段，输出这些片段元素和的最大值，以及取到该最大值的片段个数。元素可以为负数，m 最大为 2×10^5，单项绝对值最大为 10^9，累加需使用 64 位整数。

《参考解析》

第 1 题：哈希表模拟

核心是只记录「当前在库」的物品，以及它最近一次被接受的入库时刻：

• 用哈希表 inTime 存 物品编号 -> 最近一次被接受的入库时刻。
• 按 i = 1..m 扫描，被拒绝的记录同样占用一个时刻，所以时刻就是当前下标 i。
• IN a：a 已在表中说明重复入库，拒绝；否则写入 inTime[a] = i，接受。
• OUT a：a 不在表中说明无货可出，拒绝；否则停留时长为 i - inTime[a]，累加后删除该键，接受。
• 扫描结束后，哈希表大小就是剩余物品数。

每次操作只做常数次哈希查找，时间复杂度 O(m)，空间 O(m)。停留时长总和可能达到 O(m²)，必须用 long long 累加。

unordered_map<long long, long long> inTime;
long long ok = 0, bad = 0, stay = 0;
for (int i = 1; i <= m; ++i) {
    string op; long long a;
    cin >> op >> a;
    if (op == "IN") {
        if (inTime.count(a)) ++bad;
        else { inTime[a] = i; ++ok; }
    } else {
        if (!inTime.count(a)) ++bad;
        else { stay += i - inTime[a]; inTime.erase(a); ++ok; }
    }
}
cout << ok << ' ' << bad << ' ' << stay << ' ' << inTime.size() << '\n';

第 2 题：滑动窗口

相邻两个长度为 t 的片段只相差首尾各一项，因此不必每个片段重新求和：

• 先算最左边窗口 b[0..t-1] 的和，作为当前最大值，出现次数记为 1。
• 窗口右移一格：加上新进入的 b[i]，减去离开的 b[i-t]。
• 新和严格大于当前最大值时，更新最大值并把次数重置为 1；等于最大值时次数加 1。

每个元素最多进出窗口一次，时间复杂度 O(m)，空间 O(m)（保存原序列；窗口本身只用常数空间）。注意负数不能截断为 0，题目要的是代数和；当 t = m 时只有一个片段，答案就是整段之和与次数 1。