题目描述给定若干555位邮政编码可能包含无效格式需要按照美国邮政服务USPS\texttt{USPS}USPS大宗邮件Bulk Mailing\texttt{Bulk Mailing}Bulk Mailing的打包规则统计能够组成的555位捆、333位捆以及必须按普通邮件First Class\texttt{First Class}First Class寄出的信件数量。打包规则如下将信件按邮编升序排列。优先组成555位捆同一555位邮编的信件每101010151515封组成一捆。要求捆数尽可能少。剩余信件按前333位邮编分组组成333位捆同一前333位的信件同样每101010151515封组成一捆。若某个333位组内的信件总数不足101010封则不能组成333位捆全部归入普通邮件。若某组信件的数量无法用若干个101010151515的捆完全覆盖则尽可能多地打包剩余信件归入普通邮件。对于333位捆需从该前333位组中最低的邮编开始取信以确保组成捆的信件尽量来自低邮编。输入格式输入包含多行每行一个字符串代表一个邮政编码。输入以EOF\texttt{EOF}EOF结束。每个字符串长度不定可能包含非数字字符。输出格式输出需严格遵循以下格式第一行表头ZIP、LETTERS、BUNDLES分别左对齐、右对齐列宽固定。随后依次输出所有555位捆按邮编升序每行输出邮编、捆内信件总数、捆数。所有333位捆按前333位升序邮编显示为dddx333位数字加xx。普通邮件按邮编升序每行输出邮编、信件数、捆数恒为000。各组之间以及表头后、总计前均需有空行。最后输出总计行TOTALS后跟总信件数和总捆数。最后输出INVALID ZIP CODES并在下一行开始按输入顺序逐行输出每个无效邮编重复者只输出一次。样例输入95864 95864 95864 95867 95920 9j876 95616 95616 95747 95814 95818 95818 8976 95818 95818 95819 95819 00000 95819 95819 95819 95819 95819 95825 95825 95825 95825 95825 95826 95826 95826 95826 95826 95826 95827 8976 95833 95833 95833 95833 95819 95819 95819 95819 95833 95833 95833 95864 95864 95864 123456 95864 95864 95864 95864输出ZIP LETTERS BUNDLES 95819 11 1 95864 10 1 958xx 25 2 95616 2 0 95747 1 0 95920 1 0 TOTALS 50 4 INVALID ZIP CODES 9j876 8976 00000 123456题目分析本题属于模拟 贪心问题难度中等。核心在于准确实现打包规则特别注意以下几点输入处理需要逐词读取以空格或换行为分隔判断每个字符串是否为有效的555位邮编恰好555个数字且不能全为000。无效邮编需按首次出现顺序保存。打包计数对于给定数量的信件nnn求最多能组成多少个101010151515封的捆以及这些捆总共包含多少封信。若n10n 10n10无法组成捆返回(0,0)(0, 0)(0,0)。否则设k⌊n/15⌋k \lfloor n / 15 \rfloork⌊n/15⌋rn mod 15r n \bmod 15rnmod15。若r0r 0r0正好分为kkk个151515封捆。若r0r 0r0考虑是否可以将剩余rrr封信分摊到已有的151515封捆中使得每个捆仍为101010151515封。分摊后最多能组成k1k1k1个捆需要满足n≥10(k1)n \ge 10(k1)n≥10(k1)。若满足则组k1k1k1个捆总信件数为nnn否则只能组kkk个捆每捆151515封剩余rrr封信无法打包。这个贪心策略保证了捆数最少同时捆内信件数尽可能多即优先使用151515封捆。分组顺序先对所有有效邮编统计出现次数。按邮编升序遍历每个邮编对其次数调用打包函数得到555位捆的捆数和捆内信件数并记录剩余信件。将剩余信件按前333位分组每组内部按邮编升序排列因为取信时要优先取低邮编。对每个前333位组计算总剩余信件数调用打包函数得到333位捆的捆数和捆内信件数。从该组最低邮编开始依次取出用于组成333位捆的信件数量为打包函数返回的捆内信件总数剩余信件归入普通邮件。输出格式必须严格按照题目给定的列宽和对齐方式。通过std::left、std::right、std::setw控制确保与样例完全一致。解题思路第一步输入与合法性校验使用cin token逐个读取单词。定义函数判断有效邮编长度必须为555所有字符均为数字09不能全为0。有效邮编累加到std::mapstring, int中自动按邮编升序无效邮编存入vectorstring并用unordered_setstring去重。第二步统计与打包定义辅助函数computeBundle(int n)返回pairint,int捆内信件数, 捆数实现上述贪心算法。遍历有效邮编的映射已升序对每个邮编的数量cnt调用computeBundle得到(t5, b5)。若b5 0记录555位捆并累加总捆数。剩余信件rem cnt - t5若rem 0按前333位存入mapstring, vectorpairstring,int其中pair为邮编, 剩余数量。对每个前333位分组将该组内的(邮编, 数量)按邮编升序排序因map内顺序未保证需显式排序。计算该组总剩余信件数totalRem调用computeBundle得到(t3, b3)。若b3 0记录333位捆累加总捆数。从低邮编开始依次取出t3封信用于组成333位捆剩余的信件按原邮编累加到firstClassMapstd::mapstring,int中用于普通邮件输出。第三步输出使用std::setw控制列宽ZIP左对齐占888位LETTERS右对齐占111111位BUNDLES右对齐占121212位参考通过的代码。分别输出555位捆、333位捆、普通邮件每组间空行表头后、总计前各空行。最后输出无效邮编列表每行一个。复杂度分析设有效邮编种类数为MMMM≤M \leM≤输入行数每个邮编出现次数累加的总信件数为NNN。遍历所有有效邮编并调用打包函数O(M)O(M)O(M)。分组排序每个前333位组内的邮编数量总和为MMM排序总复杂度O(Mlog⁡M)O(M \log M)O(MlogM)最坏情况。总体时间复杂度为O(Mlog⁡M)O(M \log M)O(MlogM)空间复杂度O(M无效邮编数)O(M \text{无效邮编数})O(M无效邮编数)完全满足题目要求。代码实现// Bulk Mailing// UVa ID: 643// Verdict: Accepted// Submission Date: 2026-06-24// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 计算最多能组成的捆内信件数和捆数返回 {letters_in_bundles, bundle_count}pairint,intcomputeBundle(intn){if(n10)return{0,0};intkn/15;intrn%15;if(r0)return{n,k};if(n10*(k1))return{n,k1};return{15*k,k};}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);mapstring,intcountMap;// 有效邮编 - 总出现次数vectorstringinvalidList;// 按出现顺序去重存储无效邮编unordered_setstringinvalidSet;string token;while(cintoken){boolvalidtrue;if(token.length()!5)validfalse;else{boolallZerotrue;for(charc:token){if(c0||c9){validfalse;break;}if(c!0)allZerofalse;}if(validallZero)validfalse;// 全 0 无效}if(valid){countMap[token];}else{if(invalidSet.find(token)invalidSet.end()){invalidSet.insert(token);invalidList.push_back(token);}}}// 有效邮编升序排列vectorstringvalidZips;for(autop:countMap)validZips.push_back(p.first);sort(validZips.begin(),validZips.end());// 存储 5 位捆结果zip, letters, bundlesvectortuplestring,int,intfiveBundles;// 按前缀分组prefix - vector of (zip, remaining)mapstring,vectorpairstring,intprefixRemMap;inttotalLetters0;inttotalBundles0;for(conststringzip:validZips){intcntcountMap[zip];totalLetterscnt;auto[t5,b5]computeBundle(cnt);if(b50){fiveBundles.emplace_back(zip,t5,b5);totalBundlesb5;}intremcnt-t5;if(rem0){string prefixzip.substr(0,3);prefixRemMap[prefix].push_back({zip,rem});}}// 存储 3 位捆结果prefix, letters, bundlesvectortuplestring,int,intthreeBundles;mapstring,intfirstClassMap;// 最终 first class 信件zip - countfor(autoentry:prefixRemMap){string prefixentry.first;autovecentry.second;// 按邮编升序排序sort(vec.begin(),vec.end(),[](constpairstring,inta,constpairstring,intb){returna.firstb.first;});inttotalRem0;for(autop:vec)totalRemp.second;auto[t3,b3]computeBundle(totalRem);if(b30){threeBundles.emplace_back(prefix,t3,b3);totalBundlesb3;}// 从低邮编依次取 t3 封信组成 3 位捆剩下的归入 firstClassintneedt3;for(autop:vec){intremp.second;if(rem0)continue;if(need0){inttakemin(rem,need);rem-take;need-take;}if(rem0){firstClassMap[p.first]rem;}}}// ---------- 输出报告严格按给定格式 ----------// 表头列宽ZIP 左对齐 8LETTERS 右对齐 10BUNDLES 右对齐 8coutleftsetw(8)ZIPrightsetw(11)LETTERSsetw(12)BUNDLES\n;cout\n;// 标题后空行// 5 位捆if(!fiveBundles.empty()){for(autot:fiveBundles){string zip;intletters,bundles;tie(zip,letters,bundles)t;coutleftsetw(8)ziprightsetw(8)letterssetw(12)bundles\n;}cout\n;// 组间空行}// 3 位捆if(!threeBundles.empty()){for(autot:threeBundles){string prefix;intletters,bundles;tie(prefix,letters,bundles)t;coutleftsetw(8)(prefixxx)rightsetw(8)letterssetw(12)bundles\n;}cout\n;// 组间空行}// first classif(!firstClassMap.empty()){for(autop:firstClassMap){coutleftsetw(8)p.firstrightsetw(8)p.secondsetw(12)0\n;}cout\n;// 总计前空行}// 总计coutleftsetw(8)TOTALSrightsetw(8)totalLetterssetw(12)totalBundles\n;cout\n;// 无效邮编每个占一行coutINVALID ZIP CODES\n;for(conststringinv:invalidList)coutinv\n;return0;}总结本题重点在于贪心打包函数的设计需要正确处理101010151515的限制并保证捆数最少。核心是判断剩余信件能否分摊到已有的151515封捆中从而减少一个捆数。分组与排序555位捆直接按邮编升序333位捆需按前333位分组组内按邮编升序取信保证低邮编优先。输出格式的精确控制使用setw和左右对齐严格按照题目要求排版这是通过在线评测的关键细节。数据结构的运用std::map自动排序std::unordered_set去重std::tuple存储结果提高了代码可读性和效率。掌握这些模拟题的常见处理技巧能够帮助应对类似的复杂约束输出问题。