UVa 778 Recording a Tape

题目描述给定若干种可用的盒式磁带每种磁带具有固定的总时长单位分钟。现有若干首歌曲每首歌曲的时长以“分”和“秒”给出。要求从可用磁带中选取总时长最短的一种使得所有歌曲能够被分配到该磁带的A\texttt{A}A、B\texttt{B}B两个面中且每一面的歌曲总时长均不超过磁带总时长的一半。输出所选磁带的时长以及A\texttt{A}A面和B\texttt{B}B面分别包含的歌曲时长列表。输入包含多个测试实例每个实例的歌曲列表以一行%结束整个输入也以%结束。题目保证所有歌曲的时长互不相同。输入格式每个测试实例的第一行包含若干个整数表示可用磁带的时长单位分钟。接下来的若干行每行包含一首歌曲的时长格式为Xm Ys其中X和Y是非负整数表示分钟和秒。实例的歌曲列表以仅包含%的一行结束。整个输入文件以仅包含%的一行结束。输出格式对于每个测试实例输出第一行所选磁带的时长单位分钟。第二行Side A。后续若干行A 面每首歌曲的时长格式同输入。下一行Side B。后续若干行B 面每首歌曲的时长。最后一行%。样例输入56 90 120 20m 44s 4m 36s 7m 18s 13m 8s 9m 6s 8m 12s % 30 45 3m 11s 4m 45s 13m 45s 6m 8s %输出90 Side A 20m 44s 4m 36s 7m 8s Side B 13m 8s 9m 6s 8m 12s % 30 Side A 3m 11s 4m 45s 6m 8s Side B 13m 45s %题目分析本题本质上是一个划分问题将若干首歌分成两组A\texttt{A}A面和B\texttt{B}B面每组的总时长分别不超过磁带容量的一半同时要求使用的磁带总时长尽可能短。设所有歌曲总时长为SSS秒可用磁带总时长为TTT秒。磁带每面的容量为C⌊T/2⌋C \lfloor T / 2 \rfloorC⌊T/2⌋。若选择该磁带则必须存在一个子集AAA作为A\texttt{A}A面使得其总时长sumAsum_AsumA​满足sumA≤Csum_A \le CsumA​≤CS−sumA≤CS - sum_A \le CS−sumA​≤C即sumAsum_AsumA​必须落在区间[max⁡(0,S−C), C][\max(0, S-C), \ C][max(0,S−C),C]内。因此对于给定的磁带问题转化为判断是否存在子集和落在上述区间内。由于歌曲数量不多且磁带容量有限通常不超过数万秒可以用0/1\texttt{0/1}0/1背包动态规划求解所有可能的子集和并记录转移过程以便回溯出具体划分。另外对于多个可用磁带只需按总时长升序依次尝试第一个可行的即为答案因为要求最短磁带。题目中所有歌曲时长互不相同这一性质便于回溯时唯一确定歌曲但即便不唯一也不影响算法正确性。解题思路步骤一输入解析读取一行可用磁带时长用空格分隔存入vectorint并升序排序。随后逐行读取歌曲时长每行格式固定为Xm Ys通过查找字符m和s分离分钟和秒统一转换为秒数存储。遇到单独一行的%表示当前实例的歌曲列表结束。步骤二尝试磁带对于排序后的每个磁带时长tapeMintapeMintapeMin转换为秒tapeSectapeMin×60tapeSec tapeMin \times 60tapeSectapeMin×60。若tapeSecStapeSec StapeSecS则总时长不足跳过。计算容量CtapeSec/2C tapeSec / 2CtapeSec/2。使用0/1\texttt{0/1}0/1背包动态规划计算可达子集和。步骤三动态规划与回溯设dp[s]\textit{dp}[s]dp[s]表示能否凑出总秒数sss0≤s≤C0 \le s \le C0≤s≤C。同时维护两个辅助数组preSum[s]\textit{preSum}[s]preSum[s]在转移时记录得到sss的上一个状态即减去当前歌曲时长后的值。preIdx[s]\textit{preIdx}[s]preIdx[s]记录得到sss时最后加入的歌曲索引。初始dp[0]true\textit{dp}[0] \texttt{true}dp[0]true。对每首歌iii时长为ddd从CCC向下遍历sss若dp[s−d]\textit{dp}[s-d]dp[s−d]为真且dp[s]\textit{dp}[s]dp[s]为假则更新dp[s]\textit{dp}[s]dp[s]并记录前驱。遍历结束后在区间[max⁡(0,S−C),C][\max(0, S-C), C][max(0,S−C),C]内找到第一个可达和sumAsum_AsumA​即为 A 面的总时长。若不存在则当前磁带不可行继续尝试下一个。步骤四构造划分从sumAsum_AsumA​开始利用preSum\textit{preSum}preSum和preIdx\textit{preIdx}preIdx反向追踪得到A\texttt{A}A面的所有歌曲索引。剩余歌曲自动归入B\texttt{B}B面。步骤五输出按题目格式输出磁带时长、A\texttt{A}A面列表、B\texttt{B}B面列表最后输出%。复杂度分析设歌曲数为nnn磁带容量为CCC秒。每个实例的DP\texttt{DP}DP时间复杂度为O(n⋅C)O(n \cdot C)O(n⋅C)空间复杂度为O(C)O(C)O(C)。由于输入实例数量不定但CCC通常不超过几万该复杂度是可行的。若遇到较大容量需注意内存和运行时间但题目未给出明确限制此算法已足够。代码实现// Recording a Tape// UVa ID: 778// Verdict: Accepted// Submission Date: 2026-07-08// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 去除字符串首尾空格staticstringtrim(conststrings){size_t ls.find_first_not_of( \t\n\r);if(lstring::npos)return;size_t rs.find_last_not_of( \t\n\r);returns.substr(l,r-l1);}// 将形如 20m 44s 的字符串转为秒数staticintparseSongDuration(conststringline){size_t mPosline.find(m);size_t sPosline.find(s);intminutes0,seconds0;if(mPos!string::npos){string minStrline.substr(0,mPos);minStr.erase(remove(minStr.begin(),minStr.end(), ),minStr.end());minutesstoi(minStr);}if(sPos!string::npos){string secStrline.substr(mPos1,sPos-mPos-1);secStr.erase(remove(secStr.begin(),secStr.end(), ),secStr.end());secondsstoi(secStr);}returnminutes*60seconds;}// 输出一首歌的时长原格式staticvoidprintSong(inttotalSec){intmtotalSec/60;intstotalSec%60;coutmm ss;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string line;while(getline(cin,line)){linetrim(line);if(line%)break;// 整个输入结束// 读取可用磁带时长vectorintavailable;istringstreamiss(line);intval;while(issval)available.push_back(val);// 读取歌曲列表vectorintsongs;while(getline(cin,line)){linetrim(line);if(line%)break;// 当前实例结束songs.push_back(parseSongDuration(line));}inttotal0;for(intd:songs)totald;intn(int)songs.size();sort(available.begin(),available.end());// 尝试每个磁带for(inttapeMin:available){inttapeSectapeMin*60;if(tapeSectotal)continue;// 总时长必须能装下intcaptapeSec/2;// 每面容量// DP: dp[s] 是否可达preSum[s] 记录上一个和preIdx[s] 记录使用的歌曲索引vectorbooldp(cap1,false);vectorintpreSum(cap1,-1);vectorintpreIdx(cap1,-1);dp[0]true;for(inti0;in;i){intdsongs[i];for(intscap;sd;--s)if(!dp[s]dp[s-d]){dp[s]true;preSum[s]s-d;preIdx[s]i;}}intlowermax(0,total-cap);intchosenSum-1;for(intslower;scap;s)if(dp[s]){chosenSums;break;}if(chosenSum-1)continue;// 该磁带不可行尝试下一个// 回溯得到 A 面的歌曲索引vectorintsideA;intcurchosenSum;while(cur0){intidxpreIdx[cur];sideA.push_back(idx);curpreSum[cur];}// 标记 A 面已选vectorboolused(n,false);for(intidx:sideA)used[idx]true;// 输出结果couttapeMin\n;coutSide A\n;for(intidx:sideA){printSong(songs[idx]);cout\n;}coutSide B\n;for(inti0;in;i)if(!used[i]){printSong(songs[i]);cout\n;}cout%\n;break;// 找到最短磁带后跳出循环}}return0;}总结本题是一个经典的子集划分问题与背包问题紧密相关。关键点在于将磁带时长和歌曲时长统一转换为秒避免单位混淆。利用0/1\texttt{0/1}0/1背包DP\texttt{DP}DP计算所有可达子集和并通过前驱数组回溯构造具体划分。按磁带升序尝试保证第一个可行解即为最短磁带。输出格式细节较多需严格遵循题目要求。该解法思路清晰代码实现简洁适合作为背包问题与回溯技巧的练习。在实际竞赛中注意容量上限和输入解析的边界情况即可。