从一道PTA算法题看C++实战：如何用结构体+Map模拟口罩发放系统（附完整代码）-编程阁

从零构建口罩发放系统：C++结构体与STL的工程实践

在软件开发领域，将现实业务需求转化为高效可靠的代码实现，是每个程序员必须掌握的核心能力。今天，我们就以一个实际的口罩发放系统为例，探讨如何运用C++的结构体和标准模板库(STL)来构建一个完整的解决方案。

1. 需求分析与系统设计

任何优秀的代码实现都始于对需求的透彻理解。让我们先拆解这个口罩发放系统的核心业务规则：

用户信息验证：身份证号必须是18位纯数字
发放频率控制：成功领取后需间隔P天才能再次申请
优先级排序：按提交时间先后顺序发放，时间相同则按录入顺序
特殊人群记录：需单独记录身体状况异常的申请人

面对这样的需求，我们需要设计合理的数据结构来高效处理这些业务逻辑。结构体(Struct)非常适合用来封装用户的多维属性，而STL中的map容器则能帮助我们快速查找和更新用户状态。

struct Applicant { string name; string id; int health_status; // 0健康 1有症状 int apply_hour; int apply_minute; int last_issued_day = -1; // 上次发放日期，-1表示从未发放 int sequence; // 录入顺序 };

2. 核心数据结构实现

2.1 用户信息管理

我们使用map来存储所有合法用户的信息，以身份证号作为key：

map<string, Applicant> all_applicants;

这种设计带来几个显著优势：

O(log n)时间复杂度的查找效率
自动去重，确保同一身份证号只有一条记录
方便更新用户的最新状态

2.2 每日申请处理

每天的处理流程可以分为几个关键步骤：

数据录入与过滤：读取当日申请，过滤掉身份证不合法的记录
优先级排序：按时间先后和录入顺序排序
名额分配：按排序结果发放口罩，考虑间隔限制
特殊人群记录：标记身体状况异常的申请人

vector<Applicant> daily_applications; // 存储当日合法申请 // 示例：身份证验证函数 bool isValidID(const string& id) { if(id.length() != 18) return false; return all_of(id.begin(), id.end(), ::isdigit); }

3. 关键算法实现细节

3.1 排序算法定制

系统要求按申请时间排序，时间相同则按录入顺序。我们可以自定义比较函数：

bool compareApplicants(const Applicant& a, const Applicant& b) { if(a.apply_hour != b.apply_hour) return a.apply_hour < b.apply_hour; if(a.apply_minute != b.apply_minute) return a.apply_minute < b.apply_minute; return a.sequence < b.sequence; } // 使用示例 sort(daily_applications.begin(), daily_applications.end(), compareApplicants);

3.2 发放逻辑实现

口罩发放需要考虑用户的上次领取时间：

for(const auto& app : daily_applications) { if(issued_count >= daily_quota) break; auto& user = all_applicants[app.id]; if(user.last_issued_day == -1 || current_day - user.last_issued_day > P) { cout << user.name << " " << user.id << endl; user.last_issued_day = current_day; issued_count++; } }

4. 系统扩展与优化思路

4.1 性能优化建议

当处理大规模数据时，可以考虑以下优化：

使用unordered_map替代map，将查找复杂度降至O(1)
预分配vector空间避免频繁内存分配
多线程处理不同日期的数据

4.2 业务功能扩展

实际生产环境中，系统可能需要更多功能：

发放记录持久化存储
数据统计与分析报表
异常申请检测机制
用户通知系统集成

// 示例：扩展数据结构支持新功能 struct EnhancedApplicant : Applicant { vector<int> issue_history; // 发放记录 string contact; // 联系方式 int total_issued = 0; // 累计发放数量 };

5. 完整代码实现与测试

以下是整合各模块后的完整实现：

#include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; struct Applicant { string name; string id; int health; int hour, minute; int sequence; int last_issued = -1; }; bool isValidID(const string& id) { return id.length() == 18 && all_of(id.begin(), id.end(), ::isdigit); } bool compareApps(const Applicant& a, const Applicant& b) { if(a.hour != b.hour) return a.hour < b.hour; if(a.minute != b.minute) return a.minute < b.minute; return a.sequence < b.sequence; } int main() { int D, P; cin >> D >> P; map<string, Applicant> all_apps; map<string, bool> health_concerns; for(int day = 1; day <= D; day++) { int T, S; cin >> T >> S; vector<Applicant> daily; for(int i = 0; i < T; i++) { Applicant app; char sep; cin >> app.name >> app.id >> app.health >> app.hour >> sep >> app.minute; app.sequence = i; if(!isValidID(app.id)) continue; daily.push_back(app); all_apps[app.id] = app; if(app.health == 1) { health_concerns[app.id] = true; } } sort(daily.begin(), daily.end(), compareApps); int issued = 0; for(const auto& app : daily) { if(issued >= S) break; auto& user = all_apps[app.id]; if(user.last_issued == -1 || day - user.last_issued > P) { cout << user.name << " " << user.id << endl; user.last_issued = day; issued++; } } } for(const auto& [id, _] : health_concerns) { cout << all_apps[id].name << " " << id << endl; } return 0; }

6. 常见问题与调试技巧

在实现这类系统时，开发者常会遇到几个典型问题：

时间比较错误：确保正确解析和比较hh:mm格式的时间
边界条件处理：特别注意第一天和最后一天的发放逻辑
状态更新遗漏：发放后务必更新last_issued_day
性能瓶颈：大规模数据时注意选择合适的数据结构

调试时可以采用的策略：

添加详细日志输出关键变量状态
编写单元测试验证排序和发放逻辑
使用小规模测试数据逐步验证

7. 类似系统的设计模式

口罩发放系统的设计模式可以推广到许多类似场景：

预约系统：医院挂号、餐厅订位
资源分配系统：会议室预订、共享设备管理
限购系统：电商促销商品购买限制

这些系统的共同特点是：

需要管理有限的资源
有资格或优先级规则
需要防止滥用或过度使用

// 通用预约系统框架示例 template<typename Resource, typename User> class ReservationSystem { map<User, int> last_reserved; int cooldown_period; public: bool make_reservation(const User& user, int current_day) { if(last_reserved.count(user) && current_day - last_reserved[user] < cooldown_period) { return false; } last_reserved[user] = current_day; return true; } };

在实际项目中，这种基于结构体和STL容器的设计方法已经被证明是高效可靠的。它不仅代码清晰易于维护，而且性能表现优秀，能够处理相当大规模的数据。