博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【分步处理的妙处】 校练习赛Problem D——Dinner Hall (附judge地址)
阅读量:7063 次
发布时间:2019-06-28

本文共 4681 字,大约阅读时间需要 15 分钟。

链接:,密码xx316,Problem D

这个是我们队内练习比赛时出现过的一道题,比较有代表性的分步处理。思路比较好懂,同队的ZH同学WA了若干次,只是因为问号的位置不能笼统的认为是进或者是出,应该通过比较最大可进值(就是说在当前情况下最多能进入的人数,满足以后出去的人起码要等于进去的人。这样的话,对每一步的最大理论进人数进行比较即可得出最后的结果。

Description

 

The University administration plans to build a new dinner hall, to replace the several small (and rather inadequate) dinner halls spread over the campus. To estimate the number of places needed in the new dinner hall, they performed an experiment to measure the maximum total number of clients inside the existing dinner halls at any time. They hired several students as pollers, and positioned one poller at each entrance and each exit of the existing dinner halls. The pollers' task was to note in small cards the time each client entered or exited the hall (one card for each event). In each card they wrote the time, in the format HH:MM:SS, and the associated event (letter `E' for an entry, letter `X' for and exit).

The experiment started in the morning, before breakfast, and ended in the evening, after dinner. The pollers had their watches synchronized, and the halls were empty both before and after the experiment (that is, no client was inside a hall before the experiment began, and no client remained in a hall after the experiment ended). The pollers wrote exactly one card for every client who entered a hall and for every client who exited a hall.

After the experiment, the cards were collected and sent to the administration for processing. The task, however, was not as easy as planned, because two problems were detected. Firstly, the cards were bunched together in no particular order and therefore needed sorting; that is fairly easy, but time-consuming to do by hand. But what is worse is that, although all cards had a valid time, some pollers forgot to write the letter specifying the event. The University administration decided they needed help from an expert!

Given a set of cards with times and the indication of the event (the indication of the event may be missing), write a program to determine the maximum number of clients that could possibly had been inside the dinner halls in a given instant of time.

 

Input

The input contains several test cases. The first line of a test case contains one integer N indicating the number of cards collected in the experiment (2$ \le$N$ \le$64800). Each of the next N lines contains the information written in a card, consisting of a time specification, followed by a single space, followed by an event specification. A time specification has the format HH : MM : SS, where HH represents hours (06$ \le$HH$ \le$23)MM represents minutes (00$ \le$MM$ \le$59) and SS represents seconds (00$ \le$SS$ \le$59). Within a test case, no two cards have the same time. An event specification is a single character: uppercase `E' for entry, uppercase `X' for exit and `?' for unknown. Information may be missing, but the information given is always correct. That is, the times noted in all cards are valid. Also, if a card describes an entry, then a client did enter a hall at the informed time; if a card describes an exit, then a client did leave a hall at the informed time; and if a card describes an unknown event, then a client did enter or leave a hall at the informed time.

The last test case is followed by a line containing a single zero.

 

Output

For each test case in the input, your program must print a single line, containing one single integer, the maximum total number of clients that could have been inside the dinner halls in a given instant of time.

 

Sample Input

 

4 07:22:03 X07:13:22 E08:30:51 E21:59:02 X4 09:00:00 E20:00:01 X09:05:00 ?20:00:00 ?8 10:21:00 E10:25:00 X10:23:00 E10:24:00 X10:26:00 X10:27:00 ?10:22:00 ?10:20:00 ?0

 

Sample Output

 

1 2 4

代码重写了一遍,用的vector

 

#include 
#include
#include
using namespace std;int max(int a,int b){ if(a>b) return a; else return b;}class student{ public: int s; char t;};bool cmp(student a,student b){ return a.s < b.s;}bool isentry(student n) { if(n.t=='E') return true; else return false;}bool isexit(student n) { if(n.t=='X') return true; else return false;}bool isunknown(student n) { if(n.t=='?') return true; else return false;}vector
dinner;int main(){ int testcase; while(cin>>testcase && testcase!=0) { int jin=0,chu=0,unknown=0; int hour,min,sec; char tmp,t; dinner.clear(); for(int i=0;i
>hour>>tmp>>min>>tmp>>sec>>t; needin.s=hour*3600+min*60+sec; needin.t=t; if(isentry(needin)) jin++; if(isexit(needin)) chu++; if(isunknown(needin)) unknown++; dinner.push_back(needin); } sort(dinner.begin(),dinner.end(),cmp); int maxin = (unknown-(jin-chu))/2; int currentin=0; int currmax=0; for(int i=0;i

 

 

转载地址:http://yknll.baihongyu.com/

你可能感兴趣的文章
Session,cookie,localStorage
查看>>
Jenkins——持续集成服务器
查看>>
《利用Python进行数据分析·第2版》第12章 pandas高级应用
查看>>
[剑指offer] 二叉树的镜像
查看>>
ByteTCC 0.5.0-ALPHA1 发布,基于 TCC 的分布式事务管理器
查看>>
WPS Office 2019企业版全面升级,推出密级关键词和移动会议新功能
查看>>
【实操】如何安装及查看云监控
查看>>
企业上云之机房和BGP带宽篇(三)
查看>>
SEO优化:为什么要关注“网站抓取频率”?
查看>>
浅谈web接口测试
查看>>
Python——爬虫学习1
查看>>
智云大咖秀:怎样的稳定器才是摄影师的“灵魂辅助”?
查看>>
Android 学习之drawerlayout写侧滑菜单
查看>>
深度学习工程模板
查看>>
按钮点击效果总结
查看>>
从普通程序员到身价过百亿:追求长期价值的耐心,决定了你能走多远
查看>>
每周一个linux命令之---uptime详解
查看>>
Hibernate JPA简介
查看>>
第十七章:掌握网格(三)
查看>>
深入分析java web技术内幕----读书笔记(三)
查看>>