前言
在最近整理大学前两年学的内容时，突然发现了这个数据结构程序，主要目标是实时观测一个校园停车场的状态。现发布在这里，希望可以给学习的同袍们一点帮助。
题目要求
8-1 Cars on Campus
Zhejiang University has 8 campuses and a lot of gates. From each gate we can collect the in/out times and the plate numbers of the cars crossing the gate. Now with all the information available, you are supposed to tell, at any specific time point, the number of cars parking on campus, and at the end of the day find the cars that have parked for the longest time period.
Input Specification:
Output Specification:
For each query, output in a line the total number of cars parking on campus. The last line of output is supposed to give the plate number of the car that has parked for the longest time period, and the corresponding time length. If such a car is not unique, then output all of their plate numbers in a line in alphabetical order, separated by a space.
Sample Input:
16 7
JH007BD 18:00:01 in
ZD00001 11:30:08 out
DB8888A 13:00:00 out
ZA3Q625 23:59:50 out
ZA133CH 10:23:00 in
ZD00001 04:09:59 in
JH007BD 05:09:59 in
ZA3Q625 11:42:01 out
JH007BD 05:10:33 in
ZA3Q625 06:30:50 in
JH007BD 12:23:42 out
ZA3Q625 23:55:00 in
JH007BD 12:24:23 out
ZA133CH 17:11:22 out
JH007BD 18:07:01 out
DB8888A 06:30:50 in
05:10:00
06:30:50
11:00:00
12:23:42
14:00:00
18:00:00
23:59:00
Sample Output:
1
4
5
2
1
0
1
JH007BD ZD00001 07:20:09
具体代码
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
typedef struct info* INFO; //INFO is a struct pointer which points to a struct storing information about cars
struct info
{
vector<int> in; //vector in contains time the car came in
vector<int> out; //vector in contains time the car went out
int total_time; //total_time calculates the total time the car parked in the canpus
};
map<string, INFO> Map; //Map connect the plate number and corresponding struct pointer INFO
vector<int> query; //query stores the time of queries (transfer the time to seconds so it's INT)
int n, K; //n is the total number of records and K is the number of queries
//this function process the input
void ReadData()
{
cin >> n >> K;
string s1, s2; //s1 and s2 are just temporary strings
int hour, minute, second;
for (int i = 0; i < n; i++)
{
cin >> s1;
//if there is no such car information, then construct its struct info
if (!Map.count(s1))
{
INFO temp = new struct info();
Map[s1] = temp;
}
//read the time string and transfer it to hour,minute and second
cin >> s2;
hour = (s2[0] - '0') * 10 + (s2[1] - '0'); minute = (s2[3] - '0') * 10 + (s2[4] - '0'); second = (s2[6] - '0') * 10 + (s2[7] - '0');
cin >> s2;
//if it's in time then push it to the vector in and transfer the time to seconds at the same time
if (s2 == "in") (Map[s1]->in).push_back(hour * 3600 + minute * 60 + second);
else if (s2 == "out") (Map[s1]->out).push_back(hour * 3600 + minute * 60 + second);
//if it's out time then push it to the vector out and transfer the time to seconds at the same time
}
//read the queries
//transfer the time to seconds and store them
for (int i = 0; i < K; i++)
{
cin >> s2;
hour = (s2[0] - '0') * 10 + (s2[1] - '0'); minute = (s2[3] - '0') * 10 + (s2[4] - '0'); second = (s2[6] - '0') * 10 + (s2[7] - '0');
query.push_back(hour * 3600 + minute * 60 + second);
}
}
//this function delete invalid time and pair the in time and out time
void Delete_Invalid_Time()
{
map<string, INFO> ::iterator it = Map.begin(); //define an iterator to go through the map
vector<int> temp_in, temp_out; //these are temporary vectors to avoid delete particular element in vector which is slow
while (it != Map.end())
{
sort((it->second->in).begin(), (it->second->in).end()); //sort the in time vector
sort((it->second->out).begin(), (it->second->out).end()); //sort the out time vector
vector<int> ::iterator it_in, it_out; //define an iterator to go through the vector
it_in = (it->second->in).begin(); it_out = (it->second->out).begin();
temp_in.clear(); //clear temp_in to remove elements stored last loop
temp_out.clear(); //clear temp_out to remove elements stored last loop
while (it_in != (it->second->in).end() && it_out != (it->second->out).end())
{
while (*it_in > * it_out&& it_out != (it->second->out).end()) it_out++; //while out time is less than current in time, out time is invalid
if (it_out == (it->second->out).end()) break; //no out time is valid now
while (it_in < (it->second->in).end() - 1 && *(it_in + 1) <= *it_out) it_in++; //if the next time is nearer to the current out time then the next time is valid
//now *it_in and *it_out are paired valid in and out time
temp_in.push_back(*it_in); temp_out.push_back(*it_out); it_in++; it_out++;
}
it->second->in = temp_in; //refresh the vector in
it->second->out = temp_out; //refresh the vector out
it++;
}
}
//this function consider the state of every car at particular time
//so calculate the number of cars at particular time
//also calculate total times a particular car park in campus
void Decide_State_And_Time()
{
vector<int> ans1(K, 0); //ans1 stores the number of cars corresponding queries
map<string, INFO> ::iterator it = Map.begin();//define an iterator to go through the map
while (it != Map.end())
{
int query_pointer = 0; //query_pointer is the index of vector query
it->second->total_time = 0; //initialize total time of a car
for (int i = 0; i < it->second->in.size(); i++) it->second->total_time += (it->second->out)[i] - (it->second->in)[i];//calculate total time of a car
for (int i = 0; i < it->second->in.size(); i++) //decide if the car was in campus at every query time
{
while (it->second->in[i] > query[query_pointer] && query_pointer < K) query_pointer++;
if (query_pointer == K) break;
while (it->second->out[i] > query[query_pointer] && query_pointer < K) //this condition is true when the car is in campus at this time
{
ans1[query_pointer]++;
query_pointer++;
}
}
it++;
}
for (int i = 0; i < K; i++) cout << ans1[i] << '\n'; //print out the answer of queries
}
//this function defines the rules of alphabetical order when sorting
bool compare(string s1,string s2)
{
string :: iterator it1 = s1.begin(), it2 = s2.begin(); //initialize the iterator
while(*it1 == *it2) //ignore the same part
{
it1++; it2++;
}
if(isalpha(*it1) && isdigit(*it2)) return true; //letters are before digits
else if(isalpha(*it2) && isdigit(*it1)) return false; //letters are before digits
else if(isdigit(*it1) && isdigit(*it2))
{
if(*it1 > *it2) return false; //small digit is before large digit
else return true;
}else
{
if(toupper(*it1) < toupper(*it2)) return true; //Aa should be in front of Bb
else if(toupper(*it1) > toupper(*it2)) return false;
else if(*it1 < *it2) return true; //big letter is before small letter
else return false;
}
}
//this function calculate the maximal parking time and print out the cars
void Generate_Maxtime()
{
vector<string> ans2; //ans stores the cars parking with maximal time
int Max = 0; //initialize maximal time of parking
map<string, INFO> ::iterator it = Map.begin();//define an iterator to go through the map
while (it != Map.end()) //calculate maximal parking time
{
if (it->second->total_time > Max) Max = it->second->total_time;
it++;
}
it = Map.begin();
while (it != Map.end()) //put the target cars in ans2
{
if (it->second->total_time == Max) ans2.push_back(it->first);
it++;
}
sort(ans2.begin(), ans2.end(),compare); //sort ans2 in alphabetical order
for (int i = 0; i < ans2.size(); i++) cout << ans2[i] << ' '; //print out the plate numbers of targets
//transfer the maximal time to hour, minute and second
int max_hour, max_minute, max_second;
max_second = Max % 60; Max = Max / 60; max_minute = Max % 60; Max = Max / 60; max_hour = Max;
printf("%02d:%02d:%02d\n", max_hour, max_minute, max_second); //print out maximal parking time
}
int main()
{
ReadData(); //process input
Delete_Invalid_Time();//delete invalid time and pair the in time and out time
Decide_State_And_Time();//calculate the number of cars at particular time and also calculate total times a particular car park in campus
Generate_Maxtime();//calculate the maximal parking time and print out the cars
}
后记
这是Data Structure课程的最后一个大程。只要厘清各函数间关系后也不算很难。至此DS课程的大程已全部整理完毕。之后我将陆续整理ADS课程的各大程一并放上来，以望共勉