我在本地測試沒出過問題,但是放到oj系統上就runtime error,錯誤代碼11。
應該是訪問到未定義的內存,可是我查了好久都沒找到哪裡越界了,求指教
#include <cstdio>
#define Length 1600050
struct StacketNode
{
int data;
StacketNode* next;
};
class Stacket
{
private: int _size;
StacketNode* Bottom;
StacketNode* Top;
public:
Stacket();
~Stacket();
void Push(int tra);
int Pop();
int GetTop();
private:
};
Stacket::Stacket()
{
Bottom = new StacketNode();
Bottom->data = 0;
Top = Bottom;
_size = 0;
}
void Stacket::Push(int tra)
{
StacketNode* temp = new StacketNode();
temp->data = tra;
temp->next = Top;
Top = temp;
_size++;
return;
}
int Stacket::Pop()
{
StacketNode* temp;
int temint;
temp = Top;
temint = temp->data;
Top = Top->next;
Top->next;
delete temp;
_size--;
return temint;
}
int Stacket::GetTop()
{
return Top->data;
}
int main()
{
int n = 0, m = 0, b = 0, t = 0;
int trains[Length];
bool Isfeasible = true;
scanf("%d %d",&n,&m);
int Seq[Length];
Stacket* A = new Stacket();
Stacket* B = new Stacket();
for (int i = 0; i < n; i++)
{
scanf("%d", &trains[i]);
A->Push(n-i);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (B->GetTop() == trains[i])
{
B->Pop();
Seq[t++] = 1;
b--;
break;
}
else if(A->GetTop() == 0)
{
Isfeasible = false;
break;
}
else
{
if (++b <= m)
{
B->Push(A->Pop());
Seq[t++] = 0;
}
else
{
Isfeasible = false;
break;
}
}
if (Isfeasible == false)
break;
}
}
if (Isfeasible == false)
printf("No\n");
else
{
for (int i = 0; i < t; i++)
{
switch (Seq[i])
{
case 0:
printf("push\n");
break;
case 1:
printf("pop\n");
}
}
}
return 0;
}
補充OJ問題:
描述
某列車調度站的鐵道聯接結構如Figure 1所示。
其中,A為入口,B為出口,S為中轉盲端。所有鐵道均為單軌單向式:列車行駛的方向只能是從A到S,再從S到B;另外,不允許超車。因為車廂可在S中駐留,所以它們從B端駛出的次序,可能與從A端駛入的次序不同。不過S的容量有限,同時駐留的車廂不得超過m節。
設某列車由編號依次為{1, 2, ..., n}的n節車廂組成。調度員希望知道,按照以上交通規則,這些車廂能否以{a1, a2, ..., an}的次序,重新排列後從B端駛出。如果可行,應該以怎樣
的次序操作?
輸入
共兩行。
第一行為兩個整數n,m。
第二行為以空格分隔的n個整數,保證為{1, 2, ..., n}的一個排列,表示待判斷可行性的駛出序列{a1,a2,...,an}。
輸出
若駛出序列可行,則輸出操作序列,其中push表示車廂從A進入S,pop表示車廂從S進入B,每個操作占一行。
若不可行,則輸出No。
樣例
見英文題面
限制
1 ≤ n ≤ 1,600,000
0 ≤ m ≤ 1,600,000
時間:2 sec
空間:256 MB
Example 1
Input
5 2
1 2 3 5 4
Output
push
pop
push
pop
push
pop
push
push
pop
pop
Example 2
Input
5 5
3 1 2 4 5
Output
No
#define Length 1600050
int trains[Length];
int Seq[Length]; 太大導致的stack overflow,應該使用堆上的內存
int *trains=new int[Length];
int *Seq=new int[Length];