首页 > ACM题库 > HDU-杭电 > HDU 1861 游船出租-字典树-[解题报告] C++
2013
12-23

HDU 1861 游船出租-字典树-[解题报告] C++

游船出租

问题描述 :

现有公园游船租赁处请你编写一个租船管理系统。当游客租船时,管理员输入船号并按下S键,系统开始计时;当游客还船时,管理员输入船号并按下E键,系统结束计时。船号为不超过100的正整数。当管理员将0作为船号输入时,表示一天租船工作结束,系统应输出当天的游客租船次数和
平均租船时间。
注意:由于线路偶尔会有故障,可能出现不完整的纪录,即只有租船没有还船,或者只有还船没有租船的纪录,系统应能自动忽略这种无效纪录。

输入:

测试输入包含若干测试用例,每个测试用例为一整天的租船纪录,格式为
船号(1~100) 键值(S或E) 发生时间(小时:分钟)
每一天的纪录保证按时间递增的顺序给出。当读到船号为-1时,全部输入结束,相应的结果不要输出。

输出:

对每个测试用例输出1行,即当天的游客租船次数和平均租船时间(以分钟为单位的精确到个位的整数时间)。

样例输入:

1 S 08:10
2 S 08:35
1 E 10:00
2 E 13:16
0 S 17:00
0 S 17:00
3 E 08:10
1 S 08:20
2 S 09:00
1 E 09:20
0 E 17:00
-1

样例输出:

2 196
0 0
1 60

题意:

给出一个船只借出和归还的信息列表,每条信息包括船只号,借出或归还的标记(S是借出,E是归还)和时间。求每次结束时一共借出多少次船只,和平均的借出分钟。(hint: 信息中列表中可能出现,有借无还或无借有还得记录,这些记录都可以忽略)。

 

解法:

使用字典树来存储借出信息,当遇到归还信息时,就查询字典树,并统计借出船次和借出的总时间。

 

AC代码如下:

/*
	Author: ACb0y
	DateTime: 2011年2月11日10:28:45
	Type: 模拟题
	ProblemID: HDU 1861 游船出租
	Result: 3468844	2011-02-12 10:29:14	Accepted	1861	0MS	312K	2194 B	G++	ACb0y
 */
#include <iostream>
using namespace std;
/*
	字典树节点
 */
struct node 
{
	node * pNext[10];
	//借出时间
	char * pStrTime;
};
char strNum[10];
char charFlag;
char strTime[10];
node * root;
double cnt;
double totalM;
/*
	申请一个节点
 */
node * getNode()
{
	node * pNew = (node *)malloc(sizeof(node));
	memset(pNew->pNext, 0, sizeof(pNew->pNext));
	pNew->pStrTime = NULL;
	return pNew;
}
/*
	插入借出船只信息
 */
void insert(node * root, char * strNum, char * strTime)
{
	node * pCur = root;
	int len = strlen(strNum);
	int index = 0;
	for (int i = 0; i < len; ++i)
	{
		index = strNum[0] - '0';
		if (NULL == pCur->pNext[index])
		{
			pCur->pNext[index] = getNode();
		}
		pCur = pCur->pNext[index];
	}
	//这边要判断pStrTime因为有可能会发生覆盖。
	//以免内存泄露
	if (pCur->pStrTime != NULL) 
	{
		free(pCur->pStrTime);
	}
	pCur->pStrTime = (char *)malloc(strlen(strTime) + 1);
	strcpy(pCur->pStrTime, strTime);
}
/*
	规划船只时查询借出船只字典树,并统计
	cnt和totalM。
 */
void query(node * root, char * strNum, char * strTime) 
{
	node * pCur = root;
	int len = strlen(strNum);
	int index = 0;
	for (int i = 0; i < len; ++i) 
	{
		index = strNum[i] - '0';
		if (NULL == pCur->pNext[index])
		{
			return ;
		}
		pCur = pCur->pNext[index];
	}
	//没有该船的借出记录
	if (NULL == pCur->pStrTime) 
	{
		return ;
	}
	int shour;
	int shour;
	int sminute;
	int ehour;
	int eminute;
	sscanf(pCur->pStrTime, "%d:%d", &shour, &sminute);
	sscanf(strTime, "%d:%d", &ehour, &eminute);
	++cnt;
	totalM += (ehour * 60 + eminute) - (shour * 60 + sminute);
}
/*
	释放空间
 */
void clear(node * root) 
{
	if (NULL != root->pStrTime) 
	{
		free(root->pStrTime);
	}
	for (int i = 0; i < 10; ++i) 
	{
		if (NULL != root->pNext[i]) 
		{
			clear(root->pNext[i]);
		}
	}
	free(root);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	root = getNode();
	cnt = 0;
	totalM = 0;
	while (scanf("%s", strNum) != EOF) 
	{
		if (0 == strcmp(strNum, "-1")) 
		{
			break;
		}
		cin >> charFlag >> strTime;
		if (0 == strcmp(strNum, "0")) 
		{
			//这里打了个补丁,当cnt为零的时候
			//totalM / cnt会RE.
			if (0 == cnt) 
			{
				printf("0 0/n");
				continue;
			}
			printf("%.0lf %.0lf/n", cnt, totalM / cnt);
			cnt = 0;
			totalM = 0;
			clear(root);
			root = getNode();
			continue;
		}
		
		//借出船只
		if (charFlag == 'S')
		{
			insert(root, strNum, strTime);
		}
		//归还船只
		else 
		{
			query(root, strNum, strTime);
		}
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/acb0y/article/details/6180379


  1. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!