首页 > 代码库 > 题目1022：游船出租（hash简单应用）
题目1022：游船出租（hash简单应用）
问题来源
http://ac.jobdu.com/problem.php?pid=1022
问题描述
每次输入：船号（1~100） 键值（S或E） 发生时间（小时:分钟）。当船号为0时，代表一天结束；当船号为-1时，结束输入。
问题分析
这道题一开始可能会想直接用一个结构体存下所有记录，在进行处理，这样一定是会超时的，为什么呢？由于我们在判断是不是多余数据时，需要遍历整个数组，浪费了大量时间，这种做法坑定是不行的。
本题我们发现船号只在1-100，很小的范围，那么我们使用hash数组，把船号当做数组的下标，当输入为‘E’时，我们只要判断他开始是不是‘S’就知道他是不是没用的数据了。这样一轮下来就可以得到答案。
注：注意输出平均时间计算。
参考代码
//// Created by AlvinZH on 2017/5/17.// Copyright (c) AlvinZH. All rights reserved.//#include <iostream>#include <cstring>#include <cstdio>#include <cmath>using namespace std;typedef struct{ char SorE; int h; int m;}Record;Record R[105];int main(){ int id; char c; char time[6]; int sumF=0; int sumT=0; while(1){ scanf("%d",&id); if(id==-1) break; else if(id==0){ if(sumF>0) printf("%d %d\n",sumF,(int)ceil((float)sumT/sumF)); else printf("0 0\n"); for(int i=1;i<=100;i++) R[i].SorE=‘0‘; sumF=0; sumT=0; } else{ scanf("%c %s",&c,&time); if(c==‘S‘){ R[id].SorE=‘S‘; R[id].h=(time[0]-‘0‘)*10+(time[1]-‘0‘); R[id].m=(time[3]-‘0‘)*10+(time[4]-‘0‘); } else if(c==‘E‘){ if(R[id].SorE==‘S‘){ int hh=(time[0]-‘0‘)*10+(time[1]-‘0‘); int mm=(time[3]-‘0‘)*10+(time[4]-‘0‘); sumF++; sumT+=(hh-R[id].h)*60+(mm-R[id].m); } } } }}
作者： AlvinZH
出处： http://www.cnblogs.com/AlvinZH/
本人Github：https://github.com/Pacsiy/JobDu
本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
题目1022：游船出租（hash简单应用）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。