企业官网建设流程全解析

题目描述

给定若干555位邮政编码（可能包含无效格式），需要按照美国邮政服务（USPS\texttt{USPS}USPS）大宗邮件（Bulk Mailing\texttt{Bulk Mailing}Bulk Mailing）的打包规则，统计能够组成的555位捆、333位捆以及必须按普通邮件（First Class\texttt{First Class}First Class）寄出的信件数量。

打包规则如下：

• 将信件按邮编升序排列。
• 优先组成555位捆：同一555位邮编的信件，每101010～151515封组成一捆。要求捆数尽可能少。
• 剩余信件按前333位邮编分组，组成333位捆：同一前333位的信件，同样每101010～151515封组成一捆。若某个333位组内的信件总数不足101010封，则不能组成333位捆，全部归入普通邮件。
• 若某组信件的数量无法用若干个101010～151515的捆完全覆盖，则尽可能多地打包，剩余信件归入普通邮件。
• 对于333位捆，需从该前333位组中最低的邮编开始取信，以确保组成捆的信件尽量来自低邮编。

输入格式

输入包含多行，每行一个字符串代表一个邮政编码。输入以EOF\texttt{EOF}EOF结束。
每个字符串长度不定，可能包含非数字字符。

输出格式

输出需严格遵循以下格式：

• 第一行表头：ZIP、LETTERS、BUNDLES分别左对齐、右对齐（列宽固定）。
• 随后依次输出：
  1. 所有555位捆：按邮编升序，每行输出邮编、捆内信件总数、捆数。
  2. 所有333位捆：按前333位升序，邮编显示为dddx（333位数字加xx）。
  3. 普通邮件：按邮编升序，每行输出邮编、信件数、捆数（恒为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

题目分析

本题属于模拟 + 贪心问题，难度中等。核心在于准确实现打包规则，特别注意以下几点：

1. 输入处理：需要逐词读取（以空格或换行为分隔），判断每个字符串是否为有效的555位邮编（恰好555个数字，且不能全为000）。无效邮编需按首次出现顺序保存。

2. 打包计数：对于给定数量的信件nnn，求最多能组成多少个101010～151515封的捆，以及这些捆总共包含多少封信。

   • 若n<10n < 10n<10，无法组成捆，返回(0,0)(0, 0)(0,0)。
   • 否则，设k=⌊n/15⌋k = \lfloor n / 15 \rfloork=⌊n/15⌋，r=n mod 15r = n \bmod 15r=nmod15。
     • 若r=0r = 0r=0，正好分为kkk个151515封捆。
     • 若r>0r > 0r>0，考虑是否可以将剩余rrr封信分摊到已有的151515封捆中，使得每个捆仍为101010～151515封。分摊后最多能组成k+1k+1k+1个捆，需要满足n≥10(k+1)n \ge 10(k+1)n≥10(k+1)。若满足，则组k+1k+1k+1个捆，总信件数为nnn；否则只能组kkk个捆（每捆151515封），剩余rrr封信无法打包。

   这个贪心策略保证了捆数最少，同时捆内信件数尽可能多（即优先使用151515封捆）。

3. 分组顺序：

   • 先对所有有效邮编统计出现次数。
   • 按邮编升序遍历每个邮编，对其次数调用打包函数，得到555位捆的捆数和捆内信件数，并记录剩余信件。
   • 将剩余信件按前333位分组，每组内部按邮编升序排列（因为取信时要优先取低邮编）。
   • 对每个前333位组，计算总剩余信件数，调用打包函数，得到333位捆的捆数和捆内信件数。
   • 从该组最低邮编开始，依次取出用于组成333位捆的信件（数量为打包函数返回的捆内信件总数），剩余信件归入普通邮件。

4. 输出格式：必须严格按照题目给定的列宽和对齐方式。通过std::left、std::right、std::setw控制，确保与样例完全一致。

解题思路

第一步：输入与合法性校验

• 使用cin >> token逐个读取单词。
• 定义函数判断有效邮编：
  • 长度必须为555；
  • 所有字符均为数字'0'～'9'；
  • 不能全为'0'。
• 有效邮编累加到std::map<string, int>中（自动按邮编升序），无效邮编存入vector<string>，并用unordered_set<string>去重。

第二步：统计与打包

• 定义辅助函数computeBundle(int n)，返回pair<int,int>（捆内信件数, 捆数），实现上述贪心算法。
• 遍历有效邮编的映射（已升序）：
  • 对每个邮编的数量cnt调用computeBundle，得到(t5, b5)。
  • 若b5 > 0，记录555位捆，并累加总捆数。
  • 剩余信件rem = cnt - t5，若rem > 0，按前333位存入map<string, vector<pair<string,int>>>，其中pair为（邮编, 剩余数量）。
• 对每个前333位分组：
  • 将该组内的(邮编, 数量)按邮编升序排序（因map内顺序未保证，需显式排序）。
  • 计算该组总剩余信件数totalRem，调用computeBundle得到(t3, b3)。
  • 若b3 > 0，记录333位捆，累加总捆数。
  • 从低邮编开始，依次取出t3封信用于组成333位捆，剩余的信件按原邮编累加到firstClassMap（std::map<string,int>）中，用于普通邮件输出。

第三步：输出

• 使用std::setw控制列宽：ZIP左对齐占888位，LETTERS右对齐占111111位，BUNDLES右对齐占121212位（参考通过的代码）。
• 分别输出555位捆、333位捆、普通邮件，每组间空行，表头后、总计前各空行。
• 最后输出无效邮编列表，每行一个。

复杂度分析

• 设有效邮编种类数为MMM（M≤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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 计算最多能组成的捆内信件数和捆数，返回 {letters_in_bundles, bundle_count}pair<int,int>computeBundle(intn){if(n<10)return{0,0};intk=n/15;intr=n%15;if(r==0)return{n,k};if(n>=10*(k+1))return{n,k+1};return{15*k,k};}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);map<string,int>countMap;// 有效邮编 -> 总出现次数vector<string>invalidList;// 按出现顺序去重存储无效邮编unordered_set<string>invalidSet;string token;while(cin>>token){boolvalid=true;if(token.length()!=5)valid=false;else{boolallZero=true;for(charc:token){if(c<'0'||c>'9'){valid=false;break;}if(c!='0')allZero=false;}if(valid&&allZero)valid=false;// 全 0 无效}if(valid){countMap[token]++;}else{if(invalidSet.find(token)==invalidSet.end()){invalidSet.insert(token);invalidList.push_back(token);}}}// 有效邮编升序排列vector<string>validZips;for(auto&p:countMap)validZips.push_back(p.first);sort(validZips.begin(),validZips.end());// 存储 5 位捆结果：zip, letters, bundlesvector<tuple<string,int,int>>fiveBundles;// 按前缀分组：prefix -> vector of (zip, remaining)map<string,vector<pair<string,int>>>prefixRemMap;inttotalLetters=0;inttotalBundles=0;for(conststring&zip:validZips){intcnt=countMap[zip];totalLetters+=cnt;auto[t5,b5]=computeBundle(cnt);if(b5>0){fiveBundles.emplace_back(zip,t5,b5);totalBundles+=b5;}intrem=cnt-t5;if(rem>0){string prefix=zip.substr(0,3);prefixRemMap[prefix].push_back({zip,rem});}}// 存储 3 位捆结果：prefix, letters, bundlesvector<tuple<string,int,int>>threeBundles;map<string,int>firstClassMap;// 最终 first class 信件：zip -> countfor(auto&entry:prefixRemMap){string prefix=entry.first;auto&vec=entry.second;// 按邮编升序排序sort(vec.begin(),vec.end(),[](constpair<string,int>&a,constpair<string,int>&b){returna.first<b.first;});inttotalRem=0;for(auto&p:vec)totalRem+=p.second;auto[t3,b3]=computeBundle(totalRem);if(b3>0){threeBundles.emplace_back(prefix,t3,b3);totalBundles+=b3;}// 从低邮编依次取 t3 封信组成 3 位捆，剩下的归入 firstClassintneed=t3;for(auto&p:vec){int&rem=p.second;if(rem==0)continue;if(need>0){inttake=min(rem,need);rem-=take;need-=take;}if(rem>0){firstClassMap[p.first]+=rem;}}}// ---------- 输出报告（严格按给定格式） ----------// 表头，列宽：ZIP 左对齐 8，LETTERS 右对齐 10，BUNDLES 右对齐 8cout<<left<<setw(8)<<"ZIP"<<right<<setw(11)<<"LETTERS"<<setw(12)<<"BUNDLES"<<"\n";cout<<"\n";// 标题后空行// 5 位捆if(!fiveBundles.empty()){for(auto&t:fiveBundles){string zip;intletters,bundles;tie(zip,letters,bundles)=t;cout<<left<<setw(8)<<zip<<right<<setw(8)<<letters<<setw(12)<<bundles<<"\n";}cout<<"\n";// 组间空行}// 3 位捆if(!threeBundles.empty()){for(auto&t:threeBundles){string prefix;intletters,bundles;tie(prefix,letters,bundles)=t;cout<<left<<setw(8)<<(prefix+"xx")<<right<<setw(8)<<letters<<setw(12)<<bundles<<"\n";}cout<<"\n";// 组间空行}// first classif(!firstClassMap.empty()){for(auto&p:firstClassMap){cout<<left<<setw(8)<<p.first<<right<<setw(8)<<p.second<<setw(12)<<0<<"\n";}cout<<"\n";// 总计前空行}// 总计cout<<left<<setw(8)<<"TOTALS"<<right<<setw(8)<<totalLetters<<setw(12)<<totalBundles<<"\n";cout<<'\n';// 无效邮编，每个占一行cout<<"INVALID ZIP CODES\n";for(conststring&inv:invalidList)cout<<inv<<"\n";return0;}

总结

本题重点在于：

1. 贪心打包函数的设计：需要正确处理101010～151515的限制，并保证捆数最少。核心是判断剩余信件能否分摊到已有的151515封捆中，从而减少一个捆数。
2. 分组与排序：555位捆直接按邮编升序；333位捆需按前333位分组，组内按邮编升序取信，保证低邮编优先。
3. 输出格式的精确控制：使用setw和左右对齐，严格按照题目要求排版，这是通过在线评测的关键细节。
4. 数据结构的运用：std::map自动排序，std::unordered_set去重，std::tuple存储结果，提高了代码可读性和效率。

掌握这些模拟题的常见处理技巧，能够帮助应对类似的复杂约束输出问题。