Demo entry 6340456

cars

   

Submitted by anonymous on Dec 28, 2016 at 11:47
Language: C++. Code size: 4.1 kB.

#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <iostream>
using namespace std;//declare the header files and definition files

struct carRecord{  //declare the structure
	char plate[10];//record the plates of cars
	int time;  //recond the time when the car enters the campus 
	bool in;  //a boolean variable showing the condition of the car : in or out 
};

void read(vector<carRecord>*car, int N){ // function reading the record of input
	int hour,minute,second;  
	int index;  
	char condition[5];     //a string: in or out
	for(index=0;index<N;index++){  
		scanf("%s%d:%d:%d%s",(*car)[index].plate,&hour,&minute,&second,condition);  //scan the record
		(*car)[index].time=hour*3600+minute*60+second;//express the time with seconds
		(*car)[index].in=condition[0]=='i'?true:false;//judge whether the input is 'in' with the initial
	}
}

bool timeCmp(const carRecord&A,const carRecord&B){ //function which returns a boolean value
	if(strcmp(A.plate,B.plate)==0)   //if two records are from a same car, judge whether record A is earlier than record B
	  return A.time<B.time;
	else                               
	  return strcmp(A.plate,B.plate)<0; //if two records are not from a same car, use a boolean value to judge A is "smaller" than B based on ASCII to help sort 
}

bool timeSort(const carRecord&A,const carRecord&B){//use a boolean value to judge A's time is early than B's time to help sort
	return A.time<B.time;
}

int deleteUselessRecord(vector<carRecord>*car,vector<string>*longest){ //a function to neglect the meaningless records
	int timeMax=0,Tmax=0;  //Tmax is a temperal variable, timeMax is used to store the final maximum time
	string beforeCar=(*car)[0].plate;
	for(vector<carRecord>::iterator ite=(*car).begin();ite!=(*car).end();){ //iterative variable ite to scan through the vector car
		if(ite->in&&ite+1!=(*car).end()&&strcmp(ite->plate,(ite+1)->plate)==0&&!(ite+1)->in){ // consider the pair of records where car is the same and the previous in variable is in and the other is out  
			if(beforeCar==ite->plate)            //if-else used to add the time
			   Tmax+=(ite+1)->time-ite->time;
			else{
				beforeCar=ite->plate;
				Tmax=(ite+1)->time-ite->time;
			}
			if(timeMax<Tmax){    //deploy STL function to update timeMax and the vector beforecar 
				(*longest).clear();
				(*longest).push_back(beforeCar);
				timeMax=Tmax;
			}
			else if(timeMax==Tmax)    //use push_back to add meaningful record
			     (*longest).push_back(beforeCar);
		    ite+=2;
		}
		else ite=(*car).erase(ite); //use erase function when there exists meaningless record
	}
	return timeMax;
}

void answer(int K,vector<carRecord>*car){ //function to output the number of cars on the campus for each query
	int hour,minute,second;
	int count=0,findex=0;
	while(K--){
		scanf("%d:%d:%d",&hour,&minute,&second); //scan the query
		hour=hour*3600+minute*60+second;         //express it in seconds
		for(;findex<(*car).size()&&(*car)[findex].time<=hour;findex++)// traverse through the vector to work out the number of cars on the campus 
		   if((*car)[findex].in)
		     count++;
		   else 
		     count--;
		printf("%d\n",count);
	}
}

int main(){
	int N,K;   //variable for saving  the number of records and queries respectively
	scanf("%d%d",&N,&K);
	vector<carRecord>car(N);
	read(&car,N); //deploy function to read in records
	sort(car.begin(),car.end(),timeCmp);
	vector<string>longest;
	N=deleteUselessRecord(&car,&longest);  //deploy the function to neglect those useless records
	sort(car.begin(),car.end(),timeSort);
	answer(K,&car);  //deploy function answer to output the number of cars on the campus for each query
	for(vector<string>::iterator ite=longest.begin();ite!=longest.end();ite++)
	   printf("%s ",(*ite).c_str());   // print the plates of cars which stay in the campus longest
	printf("%02d:%02d:%02d\n",N/3600,N%3600/60,N%60); // print the longest length of the time which cars stays  
	system("pause");
	return 0;
}	

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).