hiho_1057_performance_log

题目大意

    给出一个函数调用日志，判断日志是否合法，且求出合法日志中函数调用的时间长度。 
题目链接:performance log

题目分析

    首先需要清除非法日志的几种情形： 
（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<iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;

unordered_map<string, int> call_count; //记录每个函数被调用的次数，START就加1，END就减1
stack<pair<string, int>> call_stack; //调用堆栈， string函数名，int为函数的本次调用在callSeq中的索引
vector<pair<string, int> > 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<string, int>(function_name, sec));
			call_stack.push(pair<string, int>(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
");
	}
	else {
		for (int i = 0; i < call_seq.size(); i++) {
			printf("%s %s
", call_seq[i].first.c_str(), int2strSec(call_seq[i].second).c_str());
		}
	}
	return 0;
}