题意分析

给定一个单线程程序运行的记录，包含有每个函数启动和结束的时间。判定该份记录是否错误，主要的错误包含：

• 记录中的时间不是单调递增的
• 一个函数的结束时间比启动时间更早
• 记录中一个函数有不对应的启动操作START或结束操作END，比如出现了START却没有对应的END，或出现了END却没有出现START。而函数的START和END应该成对出现
• 两个函数出现交叉的情况，而在单线程程序中是不会出现的，比如 A START B START A END B END

算法分析

根据上面对可能出现错误的分析，我们可以分别对每一种错误进行处理：

记录中的时间不是严格递增的

对每一条记录的时间都与前一条的时间进行比较即可判定。

一个函数的结束时间比启动时间更早

对出现的START和END标记的时间直接进行计算即可判定。

不对应的START和END

统计每个函数START和END的个数是否相等即可判定

两个函数出现交叉

本题要做的是模拟一个函数调用栈，其实际考察的内容是对于栈的理解和运用。

我们将函数启动的操作视为进栈PUSH，函数结束的操作视为出栈POP，对于一个单线程的程序来说，其函数的调用一定满足栈的过程。在出现函数A中调用函数B的情况时，函数B的结束时间一定早于函数A。这正是栈过程中先进后出原则的体现。

如果我们用栈来模拟前面的例子，则有

• A START

  Stack A

• B START

  Stack A B

• A END

  此时出现了错误，其操作为不在栈顶的A出栈。

对于正确的情况，比如：

A START B START B END A END

同样用栈来模拟时有：

• A START

  Stack A

• B START

  Stack A B

• B END

  Stack A

• A END

  Stack

因此对于第三类错误，我们需要在程序中使用栈来模拟整个过程，即可判定是否有出现错误。

总结

我们使用栈来模拟整个程序调用的过程：

首先对于每一个记录比较与前一条记录的时间。

当出现了START操作的函数直接进栈。

当出现了END操作的函数时，判定该函数是否就是栈顶的函数，若不是则表明该记录有错误。同时对于第二类操作中"出现了END却没有出现START"的情况也处理了。若出栈元素是栈顶元素时，我们在此时对其时间进行一次检查，就可以判定第一类错误。

当整个过程记录都使用栈模拟完毕后，我们还需要对当前栈内是否还有元素进行判定。若栈不为空，则出现第二类情况中"出现了START却没有对应的END"的情况。

此外在输出时，题目要求按照函数调用树深度优先的顺序依次输出每一个函数。在模拟栈的过程中，函数入栈的顺序也正是调用树的顺序，所以在处理过程中我们使用一个序列outputList来记录函数入栈的顺序，并在函数END操作时去更新该函数其运行时间。

其伪代码如下：

For i = 1 .. n
    If (i != 0 and log[i].time < log[i - 1].time)
        Return "Error"
    End If
    If log[i].Action == "START" Then
        Stack.Push(log[i])
        outputList.push(log[i].FuncName)    // 将该函数压入输出序列
    Else
        If (Stack.Size == 0 or Stack.Top.FuncName != log[i].FuncName)
            Return "Error"
        End If
        startLog = Stack.Pop()
        If startLog.Time > log[i].Time Then
            Return "Error"
        End If
        setTime(startLog.FuncName, log[i].Time - startLog.Time)
        // 记录outputList中名称为startLog.FuncName的函数的运行时间
    End If
End For

结果分析

在实际的比赛中，该题目的通过率为14%。

在选手的程序中主要出现的错误有：

• 由于本题涉及了时间格式，在时间输入输出上出现问题，导致时间计算出问题
• 未判定函数开始时间是否大于结束时间
• 模拟栈结束后未检查栈是否为空，很多选手都是因为这个原因而没有得到100分