C++上机考试冲刺（六）—设计题、业务模拟与三题实战

设计题和业务模拟题不一定需要高级算法。它们更常考查四项能力：把自然语言规则转换为状态、为每个操作选择数据结构、维持不变量，以及在边界输入下给出确定结果。

这类题代码通常较长。最危险的做法是一边读题一边堆叠 if，直到多个状态互相矛盾。本篇先给出可复用的建模流程，再实现一个预约系统，最后用三道题完成整套系列的模拟。

一、业务模拟题的六步建模法

1. 列出实体和唯一标识

先回答：系统中有哪些对象，如何唯一找到它们？

例如预约系统包含房间和预约：

• 房间由 roomId 唯一标识；
• 一条预约包含开始时间、结束时间和预约人；
• 同一房间的预约按开始时间排序。

2. 写出状态，而不是先写操作

根据查询方式选择状态结构：

roomId
└── 按 start 排序的预约集合
    ├── [start, end) -> owner
    └── [start, end) -> owner

外层按编号快速定位房间，可以使用哈希表；内层需要寻找相邻时间段，可以使用有序映射。

3. 明确定义不变量

不变量是在每次合法操作后都必须成立的条件：

• 每条预约满足 start < end；
• 同一房间的任意两个时间段不重叠；
• 使用半开区间 [start, end)，所以 [10, 20) 与 [20, 30) 可以相邻；
• 查询结果按开始时间升序输出。

4. 为每个命令写操作表

命令	输入	读取状态	修改状态	输出
BOOK	房间、起止时间、预约人	当前房间相邻预约	插入新预约	OK / INVALID / CONFLICT
CANCEL	房间、开始时间	对应预约	删除预约	OK / NOT_FOUND
QUERY	房间	该房间全部预约	无	有序列表和 END

5. 先定义错误策略

题目没有说明时，不要擅自“修复”非法输入。例如 start >= end 是拒绝、忽略还是交换端点，必须按题意处理。本文选择返回 INVALID，不会自动交换。

6. 最后分析复杂度

复杂度分析可以反向检查数据结构是否匹配数据规模。如果每次查询都扫描所有房间，而题目有 10^5 次操作，就应重新设计索引。

二、贯穿场景：会议室预约系统

1. 为什么只需检查相邻预约

同一房间的预约按开始时间排序。插入 [start, end) 时，通过 lower_bound(start) 找到第一个开始时间不小于 start 的预约：

• 它是右侧唯一可能首先冲突的预约；
• 它的前一个元素是左侧唯一可能最后冲突的预约；
• 如果这两个都不冲突，更远的预约也不会冲突。

2. 完整程序

// verify: cpp17
#include <iostream>
#include <iterator>
#include <map>
#include <string>
#include <unordered_map>

struct Booking {
    int start;
    int end;
    std::string owner;
};

enum class BookResult {
    ok,
    invalid,
    conflict
};

class ReservationSystem {
public:
    BookResult book(
        int roomId,
        int start,
        int end,
        const std::string& owner
    ) {
        if (start >= end) {
            return BookResult::invalid;
        }

        auto& schedule = schedules_[roomId];
        const auto next = schedule.lower_bound(start);

        if (next != schedule.end() && next->second.start < end) {
            return BookResult::conflict;
        }
        if (next != schedule.begin()) {
            const auto previous = std::prev(next);
            if (previous->second.end > start) {
                return BookResult::conflict;
            }
        }

        schedule.emplace(start, Booking{start, end, owner});
        return BookResult::ok;
    }

    bool cancel(int roomId, int start) {
        const auto room = schedules_.find(roomId);
        if (room == schedules_.end()) {
            return false;
        }

        const std::size_t erased = room->second.erase(start);
        if (room->second.empty()) {
            schedules_.erase(room);
        }
        return erased == 1;
    }

    void query(int roomId, std::ostream& output) const {
        const auto room = schedules_.find(roomId);
        if (room == schedules_.end() || room->second.empty()) {
            output << "EMPTY\n";
            output << "END\n";
            return;
        }

        for (const auto& [start, booking] : room->second) {
            output << start << ' '
                   << booking.end << ' '
                   << booking.owner << '\n';
        }
        output << "END\n";
    }

private:
    std::unordered_map<int, std::map<int, Booking>> schedules_;
};

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

    int operationCount = 0;
    std::cin >> operationCount;

    ReservationSystem system;
    for (int i = 0; i < operationCount; ++i) {
        std::string command;
        std::cin >> command;

        if (command == "BOOK") {
            int roomId = 0;
            int start = 0;
            int end = 0;
            std::string owner;
            std::cin >> roomId >> start >> end >> owner;

            const BookResult result = system.book(roomId, start, end, owner);
            if (result == BookResult::ok) {
                std::cout << "OK\n";
            } else if (result == BookResult::invalid) {
                std::cout << "INVALID\n";
            } else {
                std::cout << "CONFLICT\n";
            }
        } else if (command == "CANCEL") {
            int roomId = 0;
            int start = 0;
            std::cin >> roomId >> start;
            std::cout << (system.cancel(roomId, start) ? "OK\n" : "NOT_FOUND\n");
        } else if (command == "QUERY") {
            int roomId = 0;
            std::cin >> roomId;
            system.query(roomId, std::cout);
        }
    }

    return 0;
}

输入：

9
BOOK 1 10 20 alice
BOOK 1 20 30 bob
BOOK 1 15 25 carol
QUERY 1
CANCEL 1 10
BOOK 1 15 20 carol
QUERY 1
CANCEL 2 10
QUERY 2

输出：

OK
OK
CONFLICT
10 20 alice
20 30 bob
END
OK
OK
15 20 carol
20 30 bob
END
NOT_FOUND
EMPTY
END

3. 边界测试

至少覆盖：

• start == end 和 start > end；
• 空房间查询；
• 取消不存在的房间和不存在的开始时间；
• 新预约与已有预约左端、右端恰好相接；
• 新预约包含已有预约，或被已有预约包含；
• 相同开始时间重复预约。

若一个房间有 m 条预约，BOOK 和 CANCEL 的内层有序映射操作为 O(log m)，QUERY 为 O(m)。外层哈希表查找平均为 O(1)、最坏为 O(r)，其中 r 是房间数量。

三、不要为了“设计题”过度设计

上机题的目标是正确表达规则，不是展示继承层次。以下情况通常不需要抽象基类或设计模式：

• 只有一种固定业务对象；
• 命令集合在题目中已经确定；
• 没有运行时替换策略的需求；
• 一个结构体和几个函数已经能保持不变量。

适度封装仍然有价值：让状态成为类的私有成员，把 book()、cancel() 作为唯一修改入口，可以避免主流程绕过冲突检查。

四、三题模拟：执行规则

建议在第七天连续完成下面三题。先自行实现完整程序，再对照参考代码。模拟时采用比例而不是固定分钟：

1. 用约 10% 的总时间阅读三题、标记输入输出和数据范围；
2. 优先完成最确定的一题，尽早获得一次成功编译和样例通过；
3. 为中等题预留约 35% 时间，为最长的设计题预留约 45% 时间；
4. 最后至少保留 10% 时间检查边界、类型和输出格式。

如果真实题目难度顺序不同，应按“预计完成成本和正确把握”重新排序，不必机械遵循题号。

五、模拟第一题：十六进制异或校验

题目

输入 n 个两位十六进制字节，将它们逐个异或，输出两位大写十六进制校验值。任意字节格式非法时输出 INVALID。

输入：

4
01 02 0A FF

输出：

F6

参考程序

// verify: cpp17
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string>

int hexDigitValue(char ch) {
    if ('0' <= ch && ch <= '9') {
        return ch - '0';
    }
    if ('A' <= ch && ch <= 'F') {
        return ch - 'A' + 10;
    }
    if ('a' <= ch && ch <= 'f') {
        return ch - 'a' + 10;
    }
    throw std::invalid_argument("invalid digit");
}

unsigned int parseByte(const std::string& token) {
    if (token.size() != 2) {
        throw std::invalid_argument("invalid byte");
    }
    return static_cast<unsigned int>(
        (hexDigitValue(token[0]) << 4) | hexDigitValue(token[1])
    );
}

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

    int n = 0;
    if (!(std::cin >> n) || n < 0) {
        std::cout << "INVALID\n";
        return 0;
    }

    try {
        unsigned int checksum = 0;
        for (int i = 0; i < n; ++i) {
            std::string token;
            if (!(std::cin >> token)) {
                throw std::invalid_argument("missing byte");
            }
            checksum ^= parseByte(token);
        }

        std::cout << std::uppercase << std::hex
                  << std::setw(2) << std::setfill('0')
                  << checksum << '\n';
    } catch (const std::invalid_argument&) {
        std::cout << "INVALID\n";
    }
    return 0;
}

时间复杂度为 O(n)，除输入字符串外额外空间为 O(1)。检查点包括两位格式、大小写、空输入和缺少字节。

六、模拟第二题：至多 K 类事件的最长连续区间

题目

输入 n 个事件类型编号和整数 k，求最多包含 k 种不同事件类型的最长连续区间长度。k <= 0 时答案为 0。

输入：

8 2
1 2 1 3 4 3 3 2

输出：

4

参考程序

// verify: cpp17
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

int longestWindow(const std::vector<int>& events, int k) {
    if (k <= 0) {
        return 0;
    }

    std::unordered_map<int, int> frequency;
    int left = 0;
    int answer = 0;

    for (int right = 0; right < static_cast<int>(events.size()); ++right) {
        ++frequency[events[right]];

        while (static_cast<int>(frequency.size()) > k) {
            const int value = events[left];
            --frequency[value];
            if (frequency[value] == 0) {
                frequency.erase(value);
            }
            ++left;
        }

        answer = std::max(answer, right - left + 1);
    }
    return answer;
}

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

    int n = 0;
    int k = 0;
    std::cin >> n >> k;

    if (n < 0) {
        std::cout << "INVALID\n";
        return 0;
    }

    std::vector<int> events(static_cast<std::size_t>(n));
    for (int& event : events) {
        std::cin >> event;
    }

    std::cout << longestWindow(events, k) << '\n';
    return 0;
}

左右边界都只向右移动，哈希操作平均为 O(1)，因此平均时间复杂度为 O(n)，空间复杂度为 O(k)；严格地说，在收缩前的瞬间可能暂存 k + 1 种键，数量级仍为 O(k)。

最关键的边界是：计数降为 0 时必须删除键，否则 frequency.size() 不代表当前窗口的事件种类数。

七、模拟第三题：预约系统

将本文第二节的预约系统作为第三题，不复制代码重新练习。实现前先在纸面或注释中写出：

1. 半开区间 [start, end)；
2. 每个房间内部按开始时间排序；
3. 插入时只检查 lower_bound(start) 及其前驱；
4. 空房间、非法区间、冲突和不存在的取消分别输出什么；
5. BOOK、CANCEL、QUERY 的复杂度。

第二次实现时可以先不封装类，确认规则正确后再整理接口。重构不能改变已经通过测试的输入输出行为。

八、三题考试的调试顺序

1. 编译阶段

• 标准头文件是否齐全；
• 是否误用了 C++20 接口，如 contains()、Ranges 算法；
• 函数签名和返回类型是否一致；
• 自定义比较器是否可调用且参数带 const；
• 类型名、变量名与命令字符串是否拼写一致。

2. 样例阶段

不要只确认输出“看起来一样”，还要检查空格、换行、大小写和是否输出了额外调试文本。

3. 自造边界

每题至少覆盖：

• 最小合法输入；
• 空集合或长度为 0 的允许情况；
• 单元素；
• 全相等和全部不同；
• 最大值、总和与乘积的类型范围；
• 恰好在边界相等的条件；
• 不存在答案或操作对象不存在。

4. 超时与内存

先重新计算复杂度，不要首先怀疑输入输出。检查是否在循环中重复排序、复制大容器、线性查找哈希表本可索引的对象，或让一个本应单向移动的指针反复回退。

九、七天复习安排

天数	内容	最低交付
第 1 天	C++17 基础与输入输出	默写完整程序骨架，完成 3 个输入模式
第 2 天	字符串、进制、位运算、字节流	独立完成报文解析与非法输入检查
第 3 天	STL 容器和数据结构	根据操作说出容器、接口和复杂度
第 4 天	排序、查找、二分	默写比较器和最小可行答案二分
第 5 天	双指针、滑动窗口、组合模式	写出定长窗口、变长窗口和前缀和
第 6 天	设计题和业务模拟	独立完成预约系统，补齐边界测试
第 7 天	三题连续模拟	限时完成、记录错误、只复盘高频失误

如果时间允许，第二轮不要从头逐字阅读，而应遮住代码，先根据标题默写模板，再只查看写错的部分。

十、最终考前速查表

语法与类型

• 标准：C++17；正文模板使用标准头文件；
• 总和、乘积、容量、时间戳：优先检查是否需要 long long；
• 大对象只读参数：const T&；
• 范围循环修改元素：T&；只读大对象：const T&；
• std::accumulate() 需要 64 位结果：初始值 0LL。

容器

• 动态数组：std::vector；
• 键值计数：std::unordered_map；有序输出：std::map；
• 判重：std::unordered_set；
• LIFO：std::stack；FIFO：std::queue；动态最值：std::priority_queue；
• C++17 判断键存在：find(key) != end()。

算法

• 排序：std::sort(begin, end, comparator)；比较器不能使用 <=；
• 有序边界：lower_bound() 第一个 >=，upper_bound() 第一个 >；
• 最小可行答案：可行则收缩右边界，不可行则 left = middle + 1；
• 有序二元组：相向双指针；
• 连续区间：判断能否滑动维护；
• 静态区间和：前缀和；
• 下一个更大值：单调栈；窗口最值：单调队列。

提交前

• 删除调试输出；
• 检查非法或空输入是否属于题目范围；
• 测试单元素、重复值、边界相等和不存在答案；
• 检查整数溢出、下标越界、空容器访问和残留换行；
• 最后逐字核对输出格式。

十一、C++20 可选补充

如果平台明确允许 C++20，可以把 find() 判存在替换为 contains()，使用 Ranges 算法和 std::span 改善表达。但临场不要为了缩短几行代码，把已经稳定的 C++17 模板换成不熟悉的新接口。

十二、延伸练习

• LeetCode 1603：设计停车系统
• LeetCode 641：设计循环双端队列
• LeetCode 146：LRU 缓存
• LeetCode 355：设计推特

其中 LRU 缓存和“设计推特”明显高于本系列的基础冲刺范围，适合作为时间充足时的第二轮训练，不应挤占字符串、STL、二分和滑窗的复习时间。

参考资料

• C++17 工作草案 N4659
• Microsoft Learn：C++ 标准库容器
• Microsoft Learn：map 类
• Microsoft Learn：unordered_map 类
• C++ Core Guidelines