本文主要是介绍hiho一下 第五十九周 题目1 : Performance Log，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目1 : 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
描述
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不一定是按顺序，也不一定相匹配，也不一定是唯一，这就要用一个map存起来就可以判定了。
3.输出，就是按栈中出现的顺序，输出来就可以了。但还有一个坑就是，最终不一定，栈为空。
#define N 20050
#define M 256
#define maxn 205
#define MOD 1000000000000000007
int n,allN,ansNum,id[N],ans[N];
map<string,int> mymap;
stack<int> mystack;
char name[N][260],times[N][20],state[N][10],ansS[20];
int getNum(char s[]){return ((s[0] - '0') * 10 + (s[1] - '0')) * 3600+((s[3] - '0') * 10 + (s[4] - '0')) * 60+((s[6] - '0') * 10 + (s[7] - '0')) * 1 ;
}
int getTime(char s[],char e[]){return getNum(e) - getNum(s);
}
char * getS(int sid){int s1 = sid % 60,s2 = (sid/60) % 60 ,s3 = (sid/3600);ansS[2] = ansS[5] = ':';ansS[8] = '\0';ansS[0] = '0' + s3/10;ansS[1] = '0' + s3%10;ansS[3] = '0' + s2/10;ansS[4] = '0' + s2%10;ansS[6] = '0' + s1/10;ansS[7] = '0' + s1%10;return ansS;
}
int main()
{while(S(n)!=EOF){mymap.clear();allN = 0;while(!mystack.empty()) mystack.pop();fill(ans,-1);bool flag = true;ansNum = 0;FI(n){SS(name[i]);SS(times[i]);SS(state[i]);if(i >= 1 && getNum(times[i]) < getNum(times[i-1]))flag = false;if(flag){if(mymap.count(name[i])){if(state[i][0] != 'E'){flag = false;}int ind = mymap[name[i]];if(mystack.empty() || ind != mystack.top()){flag = false;}else {mystack.pop();}if(ans[ind] != -1) flag = false;ans[ind] = getTime(times[id[ind]],times[i]);}else{if(state[i][0] != 'S'){flag = false;}mymap[name[i]] = allN;id[allN] = i;mystack.push(allN);allN++;}}}if(!mystack.empty())flag = false;if(flag){FI(allN){printf("%s %s\n",name[id[i]],getS(ans[i]));}}else {printf("Incorrect performance log\n");}}return 0;
}
这篇关于hiho一下 第五十九周 题目1 : Performance Log的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
