hihoCoder week 59-1-Performance Log
题目1 : Performance Log
时间限制:8000ms
单点时限:1000ms
内存限制:256MB
描述
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 | Sample Output |
| 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 | Incorrect performance log |
本题要判断一个程序的函数调用关系是否合法。需要考虑一下几点： 1. 序列时间必须递增（经测试无需严格递增） 2. START必须在END的前面 3. 函数调用关系不能交叉，比如ABCBCA就不行，因为B调用了C，但C没结束B就结束了，对于单线程程序，显然不行 4. 因为是单线程程序，主函数A的开始和结束要是log的第一条和最后一条。 对于第3点，可以借助堆栈完成。完整代码如下： [cpp] #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<string> #include<stack> #include<map> #include<vector> #include<cstdio> using namespace std; typedef struct one_log { string name; int sec; }; void sec2str(int sec) { int hh = sec / 3600; int mm = (sec – hh * 3600) / 60; int ss = sec – hh * 3600 – mm * 60; printf("%02d:%02d:%02dn", hh, mm, ss); } int main() { freopen("input.txt", "r", stdin); int n; stack<one_log> logs; string function_name, start_end,first_name,last_name; int hh, mm, ss; char tmp_c; vector<string> seq; map<string, int> ans; bool is_correct = true; scanf("%d", &n); for (int t = 0; t < n;t++) { cin >> function_name >> hh >> tmp_c >> mm >> tmp_c >> ss >> start_end; if (t == 0) first_name = function_name; if (t == n – 1) last_name = function_name; if (!is_correct) continue; one_log l; l.name = function_name; l.sec = hh * 3600 + mm * 60 + ss; if (start_end == "START") { logs.push(l); seq.push_back(l.name); } else { one_log tmp = logs.top(); //if (l.sec <= tmp.sec) if (l.sec < tmp.sec)//不是“严格”递增的。 { is_correct = false; continue; } if (tmp.name == l.name) { ans[l.name] = l.sec – tmp.sec; logs.pop(); } else logs.push(l); } } if (!is_correct||!logs.empty()||first_name!=last_name) printf("Incorrect performance logn"); else { for (int i = 0; i < seq.size(); i++) { printf("%s ", seq[i].c_str()); sec2str(ans[seq[i]]); } } return 0; } [/cpp] 本代码提交AC，用时61MS，内存2MB。]]>