UVa 778 Recording a Tape

2026/11/2 1:34:58

题目描述

给定若干种可用的盒式磁带，每种磁带具有固定的总时长（单位：分钟）。现有若干首歌曲，每首歌曲的时长以“分”和“秒”给出。要求从可用磁带中选取总时长最短的一种，使得所有歌曲能够被分配到该磁带的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≤C
S−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背包动态规划求解所有可能的子集和，并记录转移过程以便回溯出具体划分。

另外，对于多个可用磁带，只需按总时长升序依次尝试，第一个可行的即为答案（因为要求最短磁带）。

题目中所有歌曲时长互不相同，这一性质便于回溯时唯一确定歌曲，但即便不唯一也不影响算法正确性。

解题思路

步骤一：输入解析

读取一行可用磁带时长，用空格分隔，存入vector<int>并升序排序。
随后逐行读取歌曲时长，每行格式固定为Xm Ys，通过查找字符'm'和's'分离分钟和秒，统一转换为秒数存储。
遇到单独一行的%表示当前实例的歌曲列表结束。

步骤二：尝试磁带

对于排序后的每个磁带时长tapeMintapeMintapeMin：

转换为秒tapeSec=tapeMin×60tapeSec = tapeMin \times 60tapeSec=tapeMin×60。
若tapeSec<StapeSec < StapeSec<S，则总时长不足，跳过。
计算容量C=tapeSec/2C = tapeSec / 2C=tapeSec/2。
使用0/1\texttt{0/1}0/1背包动态规划计算可达子集和。

步骤三：动态规划与回溯

设dp[s]\textit{dp}[s]dp[s]表示能否凑出总秒数sss（0≤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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 去除字符串首尾空格staticstringtrim(conststring&s){size_t l=s.find_first_not_of(" \t\n\r");if(l==string::npos)return"";size_t r=s.find_last_not_of(" \t\n\r");returns.substr(l,r-l+1);}// 将形如 "20m 44s" 的字符串转为秒数staticintparseSongDuration(conststring&line){size_t mPos=line.find('m');size_t sPos=line.find('s');intminutes=0,seconds=0;if(mPos!=string::npos){string minStr=line.substr(0,mPos);minStr.erase(remove(minStr.begin(),minStr.end(),' '),minStr.end());minutes=stoi(minStr);}if(sPos!=string::npos){string secStr=line.substr(mPos+1,sPos-mPos-1);secStr.erase(remove(secStr.begin(),secStr.end(),' '),secStr.end());seconds=stoi(secStr);}returnminutes*60+seconds;}// 输出一首歌的时长（原格式）staticvoidprintSong(inttotalSec){intm=totalSec/60;ints=totalSec%60;cout<<m<<"m "<<s<<"s";}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string line;while(getline(cin,line)){line=trim(line);if(line=="%")break;// 整个输入结束// 读取可用磁带时长vector<int>available;istringstreamiss(line);intval;while(iss>>val)available.push_back(val);// 读取歌曲列表vector<int>songs;while(getline(cin,line)){line=trim(line);if(line=="%")break;// 当前实例结束songs.push_back(parseSongDuration(line));}inttotal=0;for(intd:songs)total+=d;intn=(int)songs.size();sort(available.begin(),available.end());// 尝试每个磁带for(inttapeMin:available){inttapeSec=tapeMin*60;if(tapeSec<total)continue;// 总时长必须能装下intcap=tapeSec/2;// 每面容量// DP: dp[s] = 是否可达，preSum[s] 记录上一个和，preIdx[s] 记录使用的歌曲索引vector<bool>dp(cap+1,false);vector<int>preSum(cap+1,-1);vector<int>preIdx(cap+1,-1);dp[0]=true;for(inti=0;i<n;++i){intd=songs[i];for(ints=cap;s>=d;--s)if(!dp[s]&&dp[s-d]){dp[s]=true;preSum[s]=s-d;preIdx[s]=i;}}intlower=max(0,total-cap);intchosenSum=-1;for(ints=lower;s<=cap;++s)if(dp[s]){chosenSum=s;break;}if(chosenSum==-1)continue;// 该磁带不可行，尝试下一个// 回溯得到 A 面的歌曲索引vector<int>sideA;intcur=chosenSum;while(cur>0){intidx=preIdx[cur];sideA.push_back(idx);cur=preSum[cur];}// 标记 A 面已选vector<bool>used(n,false);for(intidx:sideA)used[idx]=true;// 输出结果cout<<tapeMin<<"\n";cout<<"Side A\n";for(intidx:sideA){printSong(songs[idx]);cout<<"\n";}cout<<"Side B\n";for(inti=0;i<n;++i)if(!used[i]){printSong(songs[i]);cout<<"\n";}cout<<"%\n";break;// 找到最短磁带后跳出循环}}return0;}