UVa 226 MIDI Preprocessing

问题分析

MIDI\texttt{MIDI}MIDI（乐器数字接口）是一种用于计算机与合成乐器之间通信的标准。本题中，我们需要处理简单的MIDI\texttt{MIDI}MIDI程序，这些程序由一系列命令组成，每条命令包含时间单位、命令类型（ON或OFF）和音符编号。

然而，许多现有音乐无法直接翻译成这种程序形式。主要存在两类问题：

1. 重复开启问题：当一个音符已经处于ON状态时，再次发送ON命令会被忽略。修复方法是在第二个ON命令之前111个时间单位插入一个OFF命令。

2. 同时开启和关闭问题：当ON和OFF命令出现在同一时间单位时，处理顺序会导致问题。修复方法是将OFF命令移动到对应ON命令之前111个时间单位。

解题思路

本题的核心是按音符编号分组处理命令，因为不同音符的命令互不影响。

数据结构设计

structcommand{inttime_unit;// 时间单位intswitches;// 1 表示 ON，0 表示 OFFintnote_number;// 音符编号boolvalid;// 该命令是否有效};

• 使用buffer映射（音符编号→\to→命令列表）来暂存每个音符的命令序列。
• 使用counter记录当前处于ON状态的命令数量，用于判断音符是否已开启。

处理流程

1. 读取输入：按行读取命令，直到遇到-1（程序分隔符）或-2$（程序终止符）。
2. 分类处理：
   • 若命令为OFF，直接加入缓冲区，计数器减111。
   • 若命令为ON，需要判断是否应直接加入或触发预处理：
     • 如果当前音符已有未配对的ON（counter>0counter > 0counter>0）或
     • 缓冲区为空或
     • 当前时间与缓冲区最后一个命令时间相同
     • 则直接将命令加入缓冲区，计数器加111。
     • 否则，调用preprocess处理当前缓冲区的命令序列，然后清空缓冲区并加入当前命令。
3. 预处理函数preprocess：
   • 将连续的ON和OFF命令配对（按输入顺序）。
   • 检查配对后的命令对，如果后一个ON的时间≤\le≤前一个OFF的时间，则调整前一个OFF的时间为后一个ON的时间减111。
   • 如果调整后的OFF时间等于对应 `ON$ 的时间，则标记这两个命令为无效（应被消除）。
   • 将有效的命令收集到全局命令列表中。
4. 排序输出：对所有有效命令按时间排序，时间相同时ON排在OFF之前（因为题目要求先处理ON再处理OFF，但输出时ON在前），音符编号小的在前。最后输出分隔符-1或-2。

排序规则

在重载<运算符时：

• 首先按时间升序排列；
• 时间相同时，ON（111）排在OFF（000）之前；
• 若命令类型相同，则按音符编号升序排列。

代码实现

// MIDI Preprocessing// UVa ID: 226// Verdict: Accepted// Submission Date: 2016-06-02// UVa Run Time: 0.050s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintON=1,OFF=0;// 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_unit<x.time_unit;// 首先按时间升序elseif(switches!=x.switches)returnswitches>x.switches;// 时间相同，ON 排在 OFF 前面elsereturnnote_number<x.note_number;// 最后按音符编号升序}};vector<command>commands;// 存储所有有效命令map<int,vector<command>>buffer;// 按音符编号分组的临时缓冲区map<int,int>counter;// 记录每个音符当前 ON 的数量// 预处理函数：对某个音符的命令序列进行修复voidpreprocess(vector<command>&program){vector<pair<command,command>>fixed;// 存储配对的 (ON, OFF) 命令对command empty;// 空命令，用作占位符// 将 ON 和 OFF 命令按顺序配对for(inti=0,currentIndex=0;i<program.size();i++){if(program[i].switches==ON)// 遇到 ON 命令，创建新的命令对fixed.push_back(make_pair(program[i],empty));else// 遇到 OFF 命令，填充到当前未完成的命令对中{fixed[currentIndex].second=program[i];currentIndex++;}}// 根据规则修复命令对for(inti=1;i<fixed.size();i++){// 情况1：后一个 ON 的时间 <= 前一个 OFF 的时间// 需要将前一个 OFF 的时间调整到后一个 ON 的时间减 1if(fixed[i].first.time_unit<=fixed[i-1].second.time_unit){fixed[i-1].second.time_unit=fixed[i].first.time_unit;fixed[i-1].second.time_unit--;fixed[i-1].second.switches=OFF;// 确保是 OFF 命令// 保留当前 ON 命令（实际上是保留其类型）fixed[i].first.switches=ON;}// 情况2：调整后的 OFF 时间等于对应 ON 的时间// 这两个命令应被消除，标记为无效if(fixed[i-1].second.time_unit==fixed[i-1].first.time_unit){fixed[i-1].second.valid=false;fixed[i].first.valid=false;}}// 将所有有效的命令收集到全局命令列表中for(inti=0;i<fixed.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!="-1"&&line!="-2"){command aCommand;istringstreamiss(line);iss>>time_unit_in>>switches_in>>note_number_in;aCommand.time_unit=time_unit_in;aCommand.switches=switches_in=="ON";// ON 为 true (1)，OFF 为 false (0)aCommand.note_number=note_number_in;aCommand.valid=true;// 初始时所有命令都有效// 如果命令是 OFF，直接加入缓冲区并减少计数器if(aCommand.switches==OFF){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_unit==buffer[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(inti=1;i<=127;i++)if(buffer[i].size()>0)preprocess(buffer[i]);// 对所有有效命令进行排序sort(commands.begin(),commands.end());// 输出修复后的 MIDI 程序for(autoit=commands.begin();it!=commands.end();it++){cout<<(*it).time_unit<<" "<<((*it).switches?"ON":"OFF");cout<<" "<<(*it).note_number<<"\n";}// 输出程序分隔符cout<<line<<"\n";// 遇到 -2 表示所有程序处理完毕if(line=="-2")break;}return0;}

算法复杂度

• 时间复杂度：O(Nlog⁡N)O(N \log N)O(NlogN)，其中NNN为命令总数，主要来自最终的排序操作。每个音符的预处理是线性的。
• 空间复杂度：O(N)O(N)O(N)，用于存储所有命令。

注意事项

1. 输入中命令的时间是非递减的，但不同音符的命令可能交错出现，因此需要按音符分组处理。
2. 当ON和OFF同时出现在同一时间时，根据题目描述，插入OFF的时间为对应ON时间减111，如果结果与前一命令冲突，则需要进一步消除。
3. 题目保证每个ON都有匹配的OFF，且每个时间、每个音符最多只有一个ON和一个OFF。