题目大意

    给出一个函数调用日志，判断日志是否合法，且求出合法日志中函数调用的时间长度。 

题目链接:

题目分析

    首先需要清除非法日志的几种情形： 

（1）日志的时间戳不是按照时间递增的顺序 

（2）函数A中调用函数B，而函数A先于函数B结束 

（3）函数没有被START过，却出现了END 

    每次输入一个日志记录，则判断时间戳是否递增； 

    维护一个调用堆栈call_stack，如果有函数START，则入栈，如果有函数END,则必须为call_stack顶部的函数，否则非法； 

    维护一个 哈希表 call_count表示函数调用的次数，如果函数F 进行START， 则call_count[F] + 1,若函数F进行END，则call_count[F] - 1。如果出现call_count[F] < 0，则非法； 

    在函数START时候，需要记录其开始时间 用 vector> callSeq记录。函数加入call_stack时候，需要知道该函数调用的次序，因此call_stack为 stack> 其中string为函数名，int为该函数在callSeq中的索引，用于在函数出栈时候在callSeq中找到该函数并记录其执行时间。

实现

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;unordered_map
            
              call_count; //记录每个函数被调用的次数，START就加1，END就减1stack
             
              
               > call_stack; //调用堆栈， string函数名，int为函数的本次调用在callSeq中的索引vector
               
                
                  > call_seq; //最后输出的
                 <调用函数，函数时间>
                  int str2intSec(char* str_time) { int h, m, s; sscanf(str_time, "%d:%d:%d", &h, &m, &s); return 3600 * h + 60 * m + s;}string int2strSec(int sec) { int h = sec / 3600; int m = sec % 3600 / 60; int s = sec % 60; char str_time[20]; sprintf(str_time, "%02d:%02d:%02d", h, m, s); return string(str_time);}int main() { int n; char function_name[260]; char timestamp[20]; char action[20]; scanf("%d", &n); getchar(); bool invalid = false; int last_timestamp = -1; for (int i = 0; i < n; i++) { scanf("%s %s %s", function_name, timestamp, action); if (invalid) continue; int sec = str2intSec(timestamp); if (sec < last_timestamp) { //sec == last_timestap，是合法的 invalid = true; continue; } last_timestamp = sec; if (strcmp(action, "START") == 0) { call_seq.push_back(pair
                  
                   (function_name, sec)); call_stack.push(pair
                   
                    (string(function_name), call_seq.size()-1)); call_count[string(function_name)] ++; } else if(strcmp(action, "END") == 0){ if (call_stack.empty()) { invalid = true; } else{ string last_func = call_stack.top().first; if (strcmp(function_name, last_func.c_str()) != 0) { invalid = true; continue; } call_count[last_func] --; if (call_count[last_func] < 0) { invalid = true; continue; } int begin_index = call_stack.top().second; int last_sec = call_seq.at(begin_index).second; call_seq.at(begin_index).second = sec - last_sec; call_stack.pop(); } } else { invalid = true; } } if (!call_stack.empty()) invalid = true; if (invalid) { printf("Incorrect performance log\n"); } else { for (int i = 0; i < call_seq.size(); i++) { printf("%s %s\n", call_seq[i].first.c_str(), int2strSec(call_seq[i].second).c_str()); } } return 0;}