问题分析MIDI\texttt{MIDI}MIDI乐器数字接口是一种用于计算机与合成乐器之间通信的标准。本题中我们需要处理简单的MIDI\texttt{MIDI}MIDI程序这些程序由一系列命令组成每条命令包含时间单位、命令类型ON或OFF和音符编号。然而许多现有音乐无法直接翻译成这种程序形式。主要存在两类问题重复开启问题当一个音符已经处于ON状态时再次发送ON命令会被忽略。修复方法是在第二个ON命令之前111个时间单位插入一个OFF命令。同时开启和关闭问题当ON和OFF命令出现在同一时间单位时处理顺序会导致问题。修复方法是将OFF命令移动到对应ON命令之前111个时间单位。解题思路本题的核心是按音符编号分组处理命令因为不同音符的命令互不影响。数据结构设计structcommand{inttime_unit;// 时间单位intswitches;// 1 表示 ON0 表示 OFFintnote_number;// 音符编号boolvalid;// 该命令是否有效};使用buffer映射音符编号→\to→命令列表来暂存每个音符的命令序列。使用counter记录当前处于ON状态的命令数量用于判断音符是否已开启。处理流程读取输入按行读取命令直到遇到-1程序分隔符或-2$程序终止符。分类处理若命令为OFF直接加入缓冲区计数器减111。若命令为ON需要判断是否应直接加入或触发预处理如果当前音符已有未配对的ONcounter0counter 0counter0或缓冲区为空或当前时间与缓冲区最后一个命令时间相同则直接将命令加入缓冲区计数器加111。否则调用preprocess处理当前缓冲区的命令序列然后清空缓冲区并加入当前命令。预处理函数preprocess将连续的ON和OFF命令配对按输入顺序。检查配对后的命令对如果后一个ON的时间≤\le≤前一个OFF的时间则调整前一个OFF的时间为后一个ON的时间减111。如果调整后的OFF时间等于对应 ON$ 的时间则标记这两个命令为无效应被消除。将有效的命令收集到全局命令列表中。排序输出对所有有效命令按时间排序时间相同时ON排在OFF之前因为题目要求先处理ON再处理OFF但输出时ON在前音符编号小的在前。最后输出分隔符-1或-2。排序规则在重载运算符时首先按时间升序排列时间相同时ON111排在OFF000之前若命令类型相同则按音符编号升序排列。代码实现// MIDI Preprocessing// UVa ID: 226// Verdict: Accepted// Submission Date: 2016-06-02// UVa Run Time: 0.050s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintON1,OFF0;// ON 和 OFF 的常量表示// 命令结构体表示一条 MIDI 指令structcommand{inttime_unit;// 命令执行的时间单位intswitches;// 命令类型1 ON, 0 OFFintnote_number;// 音符编号范围 1 到 127boolvalid;// 该命令是否有效预处理后可能被标记为无效// 排序运算符用于最终输出排序booloperator(command x)const{if(time_unit!x.time_unit)returntime_unitx.time_unit;// 首先按时间升序elseif(switches!x.switches)returnswitchesx.switches;// 时间相同ON 排在 OFF 前面elsereturnnote_numberx.note_number;// 最后按音符编号升序}};vectorcommandcommands;// 存储所有有效命令mapint,vectorcommandbuffer;// 按音符编号分组的临时缓冲区mapint,intcounter;// 记录每个音符当前 ON 的数量// 预处理函数对某个音符的命令序列进行修复voidpreprocess(vectorcommandprogram){vectorpaircommand,commandfixed;// 存储配对的 (ON, OFF) 命令对command empty;// 空命令用作占位符// 将 ON 和 OFF 命令按顺序配对for(inti0,currentIndex0;iprogram.size();i){if(program[i].switchesON)// 遇到 ON 命令创建新的命令对fixed.push_back(make_pair(program[i],empty));else// 遇到 OFF 命令填充到当前未完成的命令对中{fixed[currentIndex].secondprogram[i];currentIndex;}}// 根据规则修复命令对for(inti1;ifixed.size();i){// 情况1后一个 ON 的时间 前一个 OFF 的时间// 需要将前一个 OFF 的时间调整到后一个 ON 的时间减 1if(fixed[i].first.time_unitfixed[i-1].second.time_unit){fixed[i-1].second.time_unitfixed[i].first.time_unit;fixed[i-1].second.time_unit--;fixed[i-1].second.switchesOFF;// 确保是 OFF 命令// 保留当前 ON 命令实际上是保留其类型fixed[i].first.switchesON;}// 情况2调整后的 OFF 时间等于对应 ON 的时间// 这两个命令应被消除标记为无效if(fixed[i-1].second.time_unitfixed[i-1].first.time_unit){fixed[i-1].second.validfalse;fixed[i].first.validfalse;}}// 将所有有效的命令收集到全局命令列表中for(inti0;ifixed.size();i){if(fixed[i].first.valid)commands.push_back(fixed[i].first);if(fixed[i].second.valid)commands.push_back(fixed[i].second);}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(true){// 重置全局变量准备处理新的 MIDI 程序commands.clear(),buffer.clear(),counter.clear();inttime_unit_in,note_number_in;string switches_in;// 读取一个程序的所有命令直到遇到 -1 或 -2while(getline(cin,line),line!-1line!-2){command aCommand;istringstreamiss(line);isstime_unit_inswitches_innote_number_in;aCommand.time_unittime_unit_in;aCommand.switchesswitches_inON;// ON 为 true (1)OFF 为 false (0)aCommand.note_numbernote_number_in;aCommand.validtrue;// 初始时所有命令都有效// 如果命令是 OFF直接加入缓冲区并减少计数器if(aCommand.switchesOFF){buffer[aCommand.note_number].push_back(aCommand);counter[aCommand.note_number]--;}else// 命令是 ON{// 条件判断是否需要立即处理当前缓冲区的命令序列if(counter[aCommand.note_number]0||// 已有未配对的 ONbuffer[aCommand.note_number].size()0||// 缓冲区为空aCommand.time_unitbuffer[aCommand.note_number].back().time_unit)// 时间与最后命令相同{// 直接加入缓冲区buffer[aCommand.note_number].push_back(aCommand);counter[aCommand.note_number];}else{// 处理当前缓冲区的所有命令preprocess(buffer[aCommand.note_number]);// 清空缓冲区加入当前命令作为新序列的开始buffer[aCommand.note_number].clear();buffer[aCommand.note_number].push_back(aCommand);counter[aCommand.note_number]1;}}}// 处理剩余的缓冲区命令每个音符最后未配对的命令序列for(inti1;i127;i)if(buffer[i].size()0)preprocess(buffer[i]);// 对所有有效命令进行排序sort(commands.begin(),commands.end());// 输出修复后的 MIDI 程序for(autoitcommands.begin();it!commands.end();it){cout(*it).time_unit ((*it).switches?ON:OFF);cout (*it).note_number\n;}// 输出程序分隔符coutline\n;// 遇到 -2 表示所有程序处理完毕if(line-2)break;}return0;}算法复杂度时间复杂度O(Nlog⁡N)O(N \log N)O(NlogN)其中NNN为命令总数主要来自最终的排序操作。每个音符的预处理是线性的。空间复杂度O(N)O(N)O(N)用于存储所有命令。注意事项输入中命令的时间是非递减的但不同音符的命令可能交错出现因此需要按音符分组处理。当ON和OFF同时出现在同一时间时根据题目描述插入OFF的时间为对应ON时间减111如果结果与前一命令冲突则需要进一步消除。题目保证每个ON都有匹配的OFF且每个时间、每个音符最多只有一个ON和一个OFF。