SRM 419 DIV1 Easy - Undo ○

問題


http://community.topcoder.com/stat?c=problem_statement&pm=10054&rd=13510

2つの操作の列が与えられる。
操作は以下の2種類。
・type a 与えられたアルファベット(ここではa)をタイプする
・undo x x秒前までの操作を取り消す。

このとき、最後のこった文字列を求める。

解き方


操作は右側の操作によって打ち消されるので、
右側の方から取り消される操作を調べていく。

残ったタイプの操作が最後に残る文字列となる。

コード


class Undo {

public: string getText(vector<string> commands, vector<int> time) {
int n=commands.size();
int used[n];

memset(used,0,sizeof(used));

for(int i=n-1;i>=0;i--)if(!used[i]){
stringstream out(commands[i]);
string c;
int num;
out>>c>>num;
if(c=="undo"){
int e=time[i]-num;
used[i]=1;
for(int j=i-1;j>=0;j--)if(e<=time[j])used[j]=1;
}
}

string ret="";
for(int i=0;i<n;i++)if(!used[i]){
stringstream out(commands[i]);
string tmp;
char ch;
out>>tmp>>ch;
ret+=ch;
}

return ret;
}

};

Share this

Related Posts

Previous
Next Post »