题的链接：P3952 时间复杂度
题解： 还是看一下上一次写的题解吧，for循环和E的匹配相当于括号匹配，用到栈的结构。点击这里！
注意点：
输入一行用getline，若前面输入用了cin，要用getchar来接收一下空格；本题的次数小于100，并非1位，所以用substr不能substr(t + 1，1)这样，应该substr(t + 1)这样；栈的存储建议从1开始。每次输入一行for循环，首先要判断是否有语法错误，再分别处理F和E;E的时候需要退栈，退栈要保证栈不为空，另行判断，栈空则ERR;循环区间x到y并不仅仅只有1位数，可能10~n，所以不能用char 类型来获取，也不能简单的通过下标来获取，用到了sstream的stringstream，按空格赋值；遇到F要先判断变量是否出现过，即扫描一次栈的内容，还要判断上一次保存的time是否有语法错误，然后将当前time累加上次time压入栈中，更新max_O;最后要判断一下栈空不空，匹配是否成功，不成功则为ERR;
知识点：头文件：sstream，sin可以随便换，意思是从str里面按空格读取赋值到f i x y ;
string str
;
getline(cin
, str
);
stringstream
sin(str
);
string f
, i
, x
, y
;
sin
>> f
>> i
>> x
>> y
;
cout
<< f
<< i
<< x
<< y
;
参考代码：
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std
;
int T
, n
, tt
;
pair
<char, int> stk
[110];
string On
, str
;
int get_n(string s
)
{
if(s
== "O(1)") return 0;
int t
= s
.find('^');
string ss
= s
.substr(t
+ 1);
return atoi(ss
.c_str());
}
int get_time(string x
, string y
)
{
if(x
== "n")
{
if(y
== "n") return 0;
else return -1;
}
else
{
if(y
== "n") return 1;
}
int a
= atoi(x
.c_str()), b
= atoi(y
.c_str());
if(a
<= b
) return 0;
else return -1;
}
bool have(char c
)
{
for(int i
= 1; i
<= tt
; i
++)
if(stk
[i
].first
== c
)
return true;
return false;
}
int main()
{
cin
>> T
;
while(T
--)
{
cin
>> n
>> On
;
getchar();
int t
= get_n(On
);
int max_O
= 0;
bool err
= false;
while(n
--)
{
getline(cin
, str
);
if(err
) continue;
if(str
== "E")
{
if(tt
) tt
--;
else err
= true;
}
else
{
stringstream
sin(str
);
string f
, i
, x
, y
;
sin
>> f
>> i
>> x
>> y
;
if(have(i
[0])) err
= true;
else
{
int time
= get_time(x
, y
);
if(time
>= 0 && stk
[tt
].second
>= 0)
time
+= stk
[tt
].second
;
else time
= -1;
stk
[++tt
] = {i
[0], time
};
max_O
= max(max_O
, time
);
}
}
}
if(tt
) err
= true, tt
= 0;
if(err
) cout
<< "ERR" << endl
;
else if(max_O
== t
) cout
<< "Yes" << endl
;
else cout
<< "No" << endl
;
}
return 0;
}
