题目
先判断是否有解,然后开两个栈,分别存进入递归时间复杂度为O(1)的变量,和时间复杂度为O(n)的变量,最后取最大值。
#include <bits/stdc++.h>
using namespace std;
int T;
int tong[1000100];
stack <int> s, s2;
int main()
{
// freopen("Time.txt", "w", stdout);
scanf("%d", &T);
while (T--)
{
memset(tong, 0, sizeof(tong));
while (s.size()) s.pop();
int L, flag = 0, F1 = 0, E1 = 0, ans = 0, now = 0; string TI;//flag为2则不进入
cin >> L >> TI; int len = TI.size();
if (TI[2] == '1')
ans = 0;
else
for (int i = 4; i < len; i++)
{
if (TI[i] >= '0' && TI[i] <= '9')
ans = ans * 10 + TI[i] - '0';
}
for (int i = 1; i <= L; i++)
{
char c1;
cin >> c1;
if (c1 == 'F')
{
F1++;
string st, ed; char bianliang;
cin >> bianliang >> st >> ed;
if (tong[bianliang - '0'])//如果已经进入了该变量,就判断ERR
flag = 1;//以后的都不计入时间复杂度 (
if (st[0] == 'n' && ed[0] != 'n' && flag != 1)
{
/*if (ed[0] == 'n')
now += 0;
else if (!flag)
now++;*/
flag = 2;
tong[bianliang - '0'] = 0;
}
else if (st[0] != 'n') //说明此时st是数
{
int sta = 0, eda = 0;
for (int i = 0; i < st.size(); i++)
if (st[i] <= '9' && st[i] >= '0')
sta = sta * 10 + st[i] - '0';
if (ed[0] == 'n' && !flag)
{
tong[bianliang - '0'] = 1;
s.push(bianliang - '0');
int SI = s.size();
now = max(now, SI);
}
else
{
for (int i = 0; i < ed.size(); i++)
if (ed[i] <= '9' && ed[i] >= '0')
eda = eda * 10 + ed[i] - '0';
if (sta > eda && flag != 1) flag = 2, s.push(214748);
if (sta <= eda) tong[bianliang - '0'] = 1, s2.push(bianliang - '0');// s2表示进去但不加时间复杂度的
}
}
}
else
{
E1++; int ha = 0;
if (s.size() )
ha = s.top(), s.pop();
else if (!s.size() && s2.size() )
ha = s2.top(), s2.pop();
tong[ha] = 0;
if (ha == 214748 && flag != 1)
flag = 0;
}
}
if (F1 != E1 || flag == 1)
printf("ERR\n");
else
{
if (ans != now)
printf("No\n", ans, now);
else
printf("Yes\n");
}
}
return 0;
}