鏈接： 點擊打開鏈接 ，密碼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 N 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 HH 23) ,? MM ?represents minutes? (00 MM 59) ?and? SS ?represents seconds? (00 SS 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 X
07:13:22 E
08:30:51 E
21:59:02 X
4
09:00:00 E
20:00:01 X
09:05:00 ?
20:00:00 ?
8
10:21:00 E
10:25:00 X
10:23:00 E
10:24:00 X
10:26:00 X
10:27:00 ?
10:22:00 ?
10:20:00 ?
0
?
Sample Output
?
1
2
4
代碼重寫了一遍，用的vector
?
#include <iostream>
#include <vector>
#include <algorithm>
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<student> 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<testcase;i++)
{
student needin;
cin>>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<dinner.size();i++)
{
if(isentry(dinner[i]))
currentin++;
if(isexit(dinner[i]))
currentin--;
if(isunknown(dinner[i]))
{
if(maxin!=0)
{
currentin++;
maxin--;
}
else
currentin--;
}
currmax=max(currmax,currentin);
}
cout<<currmax<<endl;
}
return 0;
}
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
