[hihoCoder] Performance Log

描述

You are given a txt file, which is performance logs of a single-threaded program.

Each line has three columns as follow:

[Function Name] [TimeStamp] [Action]

[FunctionName] is a string of length between 1~255

[TimeStamp] format is hh:mm:ss

Valid values for “Action” column are START or END, marking the start or end of a function call.

Each function will only be called once.

Output the depth-first traversal result of the call graph with the total time of each function call. However, sometimes the performance log isn’t correct and at that time you just need to output “Incorrect performance log”.

输入

The input only contains 1 case, first line is a positive number N representing the number of logs(1 <= N <= 20000), then there are N lines in next, each line is the log info containing [Function Name] [TimeStamp] [Action], [Function Name] is a string, you can assume the [Function Name] is distinct and the length between 1~255.

输出

Output the depth-first traversal result of the call graph with the total time of each function call for the correct performance, or output “Incorrect performance log”.

提示

A call graph is a directed graph that represents calling relationships between subroutines in a computer program.

Call graph for the sample input is shown as below:

Another sample test case.

Sample Input

8
FuncA 00:00:01 START
FuncB 00:00:02 START
FuncC 00:00:03 START
FuncA 00:00:04 END
FuncB 00:00:05 END
FuncD 00:00:06 START
FuncD 00:00:07 END
FuncC 00:00:08 END

Sample Output

Incorrect performance log

样例输入

8
FuncA 00:00:01 START
FuncB 00:00:02 START
FuncC 00:00:03 START
FuncC 00:00:04 END
FuncB 00:00:05 END
FuncD 00:00:06 START
FuncD 00:00:07 END
FuncA 00:00:08 END

样例输出

FuncA 00:00:07
FuncB 00:00:03
FuncC 00:00:01
FuncD 00:00:01
EmacsNormalVim

讲一下思路,从callgraph log的规律里找到最顶层的最后结束,即先进后出,决定了下来用栈模拟
顺序因为是不定的,我们很难查找顺序,用map保存顺序即可

我发现 index[name] = index.size(); 这样的代码会先给 index 的 key 添加 value, 再取index.size()

重要: 有一些细节的地方一定要容错,结束了检查栈是否为空,还有beginTs是否比endTs小,都要检查
大模拟的题目基本上就考是不是能注意到这些细节

AC代码

int main() { _ //debug
    int n;
    cin >> n;
    string name, time, flag;
    int h, m, s;
    char colon;
    stack<pair<string, int> > stk;
    vector<pair<string, int> > ans(n / 2 + 1);
    map<string, int> index;
    bool correct = true;
    for (int i = 0; i < n; i++) {
        cin >> name >> h >> colon >> m >> colon >> s >> flag;
        if (!correct) break;
        if (flag == "START") {
            int beginTs = h * 3600 + m * 60 + s;

            stk.push(make_pair(name, beginTs));
            if (index.count(name)) {
                correct = false;
            }
            int k = index.size();
            index[name] = k;
        }
        else {
            if (stk.empty()) {
                correct = false;
            }
            pair<string, int> top = stk.top();
            if (name != top.first) {
                correct = false;
            }

            stk.pop();
            int endTs = s + m * 60 + h * 3600;
            int pos = index[name];
            if (endTs < top.second) {
                correct = false;
            }
            ans[pos] = make_pair(name, endTs - top.second);
        }
    }
    if (!stk.empty()) {
        correct = false;
    }
    if (!correct) {
        cout << "Incorrect performance log" << endl;
    }
    else {
        for (int i = 0; i < n / 2; i++) {
            cout << ans[i].first << " ";
            int ms = ans[i].second;
            int h = ms / 3600;
            int m = (ms % 3600) / 60;
            int s = ms % 60;
            cout << setw(2) << setfill('0') << h << ':';
            cout << setw(2) << setfill('0') << m << ':';
            cout << setw(2) << setfill('0') << s << endl;
        }
    }
    return 0;
}