問題
http://community.topcoder.com/stat?c=problem_statement&pm=10054&rd=13510
２つの操作の列が与えられる。
操作は以下の２種類。
・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;
}
};
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
SRM 491 DIV1 Easy - FoxMakingDice
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11234&rd=14244
解き方
Kを固定することで、そのKを作ることのできる組- SRM 398 DIV1 Easy - CountExpressions
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8157&rd=12170
解き方
O（4! * 3^3）なので全探索可能。
ｘ
- SRM 588 DIV1 Easy - GUMIAndSongsDiv1
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12706&rd=15700
解き方
どの範囲のトーンを利用するか、という情報がわ
- SRM 478 DIV1 Easy - CarrotJumping
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11022&rd=14187
解き方
４x＊３を３回繰り返したときに８x＋７の２回