首页 > 试题广场 > Cars on Campus (30)
[编程题]Cars on Campus (30)
  • 热度指数:6162 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
Zhejiang University has 6 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.

输入描述:
Each input file contains one test case.  Each case starts with two positive integers N (<= 10000), the number of records, and K (<= 80000) the number of queries.  Then N lines follow, each gives a record in the format
plate_number hh:mm:ss status
where plate_number is a string of 7 English capital letters or 1-digit numbers; hh:mm:ss represents the time point in a day by hour:minute:second, with the earliest time being 00:00:00 and the latest 23:59:59; and status is either in or out.
Note that all times will be within a single day. Each "in" record is paired with the chronologically next record for the same car provided it is an "out" record. Any "in" records that are not paired with an "out" record are ignored, as are "out" records not paired with an "in" record. It is guaranteed that at least one car is well paired in the input, and no car is both "in" and "out" at the same moment. Times are recorded using a 24-hour clock.

Then K lines of queries follow, each gives a time point in the format hh:mm:ss. Note: the queries are given in ascending order of the times.


输出描述:
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.
示例1

输入

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

输出

1
4
5
2
1
0
1
JH007BD ZD00001 07:20:09
本文来自鄙人博客,如果喜欢不妨去看看,还有其他PAT题解,觉得这篇有用的话不妨去逛逛  http://blog.csdn.net/sinat_29278271
       想一道新题目没想出来,那就来写一篇解题报告吧。这道题思路上并不难,主要就是繁琐。第一遍写的时候,我当场就蒙了,这个要多大的代码量啊,然后写了100多几十行的代码,细节之处晦涩无比,最后有一个测试点过不去,但是那段让人崩溃的代码我实在是不想去看了。第二次去写他已经是一个月后的事了,主要的区别是用熟了stl,好吧,我承认我是一个懒人。
       这道题目实际上是两道题目,一是统计每个时间校园内有多少辆车,而是找出在校园内呆的时间最久的车。谢天谢地这里的时间单位是秒,总长是一天,开一个int * sumcnt = int[24*60*60]的数组,一辆车子在A时间进入了,就在sumcnt[A]++,在A时间出去了,就在sumcnt[A]--,然后每个时间段校园内车子的数目实际上对应于这个数组的前缀和,因为数据一次性给出,所以用不着树状数组处理前缀和,将数组处理成前缀和就好了。
     第二个问题的话,因为懒,直接使用了map<string,int> 建立一个从车辆名称到他在学校的停留总时间的映射。每次发现一个合理的停留区间,就将这段时间间隔加在对应的名字,map中int会被初始化为0,所以可以直接加。然后呢,然后把代码写完就可以了。
     
# include <cstdio>
# include <algorithm>
# include <string>
# include <map>
# include <iostream>
# include <vector>
using namespace std;

const int debug = 0;
const int size = 10050;
const int range = 24*60*60;

int sumcnt[range];
string ToWatch(int time_point)
{
    char str[50];
    sprintf(str,"%02d:%02d:%02d",time_point/60/60,time_point%(60*60)/60,time_point%60);
    return string(str);
}
struct Log
{
    string name;
	int type;
    int time;
    void Print()
    {
	    cout << name << ' ' << ToWatch(time) << ' ' << type << endl;
	}
    bool match (const Log& cmper) const
      {
	    return name==cmper.name&&time<cmper.time&&type==0&&cmper.type==1;  
	  }
    bool operator < (const Log& cmper) const
      {
	    if (name!=cmper.name)
	        return name < cmper.name;
        else if (time != cmper.time)
            return time < cmper.time;
        else 
            return type <  cmper.type;
	  }
} car_log[size];
int ToDec(int hour,int min,int sec)
{
    return ( hour * 60 + min)*60 + sec;
}

typedef pair<int,int> time_range;
int main ()
{
	int i,j;
	int n,k;
    scanf("%d%d",&n,&k);
    string tmp;
    for (i=0;i<n;i++)
      {
        cin >> car_log[i].name;
		int hour,min,sec;
		scanf("%d:%d:%d",&hour,&min,&sec);
        car_log[i].time = ToDec(hour,min,sec);
        cin >> tmp;
		car_log[i].type = tmp == "out";
	  }
     sort(car_log,car_log+n);if (debug)for (i=0;i<n;i++) car_log[i].Print();
     map<string,int > index;
     int maxrange = -1;
     for (i=0;i<n;i++)
       {
	     if (i+1<n&&car_log[i].match(car_log[i+1]))
           {
			 index[car_log[i].name] += car_log[i+1].time - car_log[i].time;
			 if (index[car_log[i].name] > maxrange)    maxrange = index[car_log[i].name];
			 sumcnt[car_log[i].time]++,sumcnt[car_log[i+1].time]--;
	       }
	   }
     for (i=1;i<range;i++)
       sumcnt[i] += sumcnt[i-1]; 
     while (k--)
     {
	   int hour,min,sec;
	   scanf("%d:%d:%d",&hour,&min,&sec);
	   printf("%d\n",sumcnt[ToDec(hour,min,sec)]);
	 }
	 map<string,int>::iterator it;
	 for (it = index.begin();it!=index.end();it++)
	   if (it->second==maxrange)
	      cout << it->first << ' ';
	 cout << ToWatch(maxrange) << endl;   
     return 0; 
}


编辑于 2015-08-29 12:58:15 回复(5)
//小白没用map...看到大家都用map一脸懵逼
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct info{
    char plate[10];             //车牌号
    int time;                   //以s为单位记录的时间
    bool status;                //in或者out
}t[10010],s[10010];             //t为所有记录,s为有效记录
bool cmp(info a,info b){
    if(strcmp(a.plate,b.plate)!=0)
        return strcmp(a.plate,b.plate)<0;
    else return a.time<b.time;
}
bool cmptime(info a,info b){
    return a.time<b.time;
}
int main(){
    int x,y;scanf("%d %d",&x,&y);
    int hh,mm,ss;
    for(int i=0;i<x;i++){
        char str[5];
        scanf("%s %d:%d:%d %s",t[i].plate,&hh,&mm,&ss,str);
        if(strcmp(str,"in")==0) t[i].status=true;
        else t[i].status=false;
        t[i].time=hh*3600+mm*60+ss;
    }
    sort(t,t+x,cmp);         //将所有记录以车牌号和时间排序
    
    int sumtime=0,num=0;     //sumtime为每个车牌停留的总时间,num为有效记录数
    int n=0,m=0,longest=-1;  //m为停留时间最长的所有车牌号中的起始位置,longest为最长停留时间
    char lstplate[5010][10]; //记录停留时间最长的车牌号
    for(int i=0;i<x;i++){
        if(strcmp(t[i].plate,t[i+1].plate)==0){                //i和i+1为同一辆车
            if(t[i].status==true && t[i+1].status==false){     //且i为in记录,i+1为out记录
                    int second=t[i+1].time-t[i].time;
                    sumtime+=second;                           //此次停留时间加入到此车停留总时间
                    s[num++]=t[i];
                    s[num++]=t[i+1];                           //将本次配对的两个记录加入到有效数组
            }
        }
        else{                                                  //i和i+1不是同一辆车(是时候清算i车是否有资格加入最长时间车牌中了!)
            if(sumtime>=longest){
                if(sumtime>longest){                           //更新最长停留时间与该时间首个车牌号下标 
                    m=n;
                    longest=sumtime;
                }
                strcpy(lstplate[n++],t[i].plate);               //加入到最长停留时间车牌号数组中
            }
            sumtime=0;                                         //清空总时间
        }
    }
    sort(s,s+num,cmptime);                   //将所有有效记录按时间前后排序
    int numcar=0;                            //numcar为当前停留的车辆数
    for(int i=0,j=0;i<y;i++){
        scanf("%d:%d:%d",&hh,&mm,&ss);
        int time=hh*3600+mm*60+ss;
        while(j<num && s[j].time<=time){     //j指向不超过当前查询时间的记录
            if(s[j].status) numcar++;        //车进
            else numcar--;                   //车出
            j++;
        }
        printf("%d\n",numcar);
    }
    for(int i=m;i<n;i++)                    //输出所有最长停留时间的车牌号
        printf("%s ",lstplate[i]);              
    printf("%02d:%02d:%02d",longest/3600,longest%3600/60,longest%60);  //输出最长停留时间

    return 0;
}


发表于 2018-01-24 02:09:30 回复(0)
题目是不难,思路一下子就会有,就是老是超时,超时超时
发表于 2016-10-22 12:28:44 回复(2)
比较简洁的解法,不过懒得写注释了。。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
#define MAXN 10000
#define MAXT 24*3600
using namespace std;
struct Car {
    char id[8];
    int time;
    bool in;
} car[MAXN];
int t[MAXT];
map<string, int> sumtime;
bool comp(Car a, Car b);

int main(void) {
    int n, k, h, m, s, i;
    
    scanf("%d%d", &n, &k);
    for (i = 0; i < n; i++) {
        char status[5];
        scanf("%s %d:%d:%d %s", car[i].id, &h, &m, &s, status);
        car[i].time = h * 3600 + m * 60 + s;
        car[i].in = (strcmp(status, "in") == 0);
    }
    sort(car, car+n, comp);
    int maxtime = 0;
    for (i = 0; i < n-1; i++) {
        if (!strcmp(car[i].id, car[i+1].id)) {
            if (car[i].in && !car[i+1].in){
                sumtime[car[i].id] += (car[i+1].time - car[i].time);
                t[car[i].time]++;
                t[car[i+1].time]--;
            }
        }
        maxtime = max(maxtime, sumtime[car[i].id]);
    }
    for (i = 1; i < MAXT; i++) 
        t[i] += t[i-1];   
    for (i = 0; i < k; i++) {
        scanf("%d:%d:%d", &h, &m, &s);
        int t_query = h * 3600 + m * 60 + s;
        printf("%d\n", t[t_query]);
    }
    map<string, int>::iterator iter;
    for (iter =sumtime.begin(); iter != sumtime.end(); iter++) {
        if (iter->second == maxtime) 
            cout<<iter->first<<" ";	
    }
    printf("%02d:%02d:%02d\n", maxtime / 3600, maxtime % 3600 / 60, maxtime % 60);
    
    return 0;
}
bool comp(Car a, Car b) {
    if (strcmp(a.id, b.id))     return strcmp(a.id, b.id) < 0;
    else                        return a.time < b.time;
}

发表于 2017-08-16 20:22:07 回复(0)
思路和一楼差不多,最开始用树状数组怼了半天,一直超时,后来换了前缀和,但PTA平台上第四个点一直过不去,估计牛客上的就是这个数据,后来对这组测试数据有一点猜测,应该包含进在出之后的情况,像是这样:
JH007BD 18:00:01 in
JH007BD 18:00:00 out
必须判断in的时间严格小于out的时间
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;
long long n, m;
const int maxn = 9e5 + 5;
const int N = 1e4 + 5;
long long a[maxn];

struct cmd
{
    string name, ope;
    int time;
    bool match(const cmd &cmper) const
    {
        return name == cmper.name && time < cmper.time && ope[0] == 'i' && cmper.ope[0] == 'o';
    }
    bool operator<(cmd &c)
    {
        if (name == c.name)
        {
            return time < c.time;
        }
        else
        {
            return name < c.name;
        }
    }
} cmds[N];

map<string, int> mp;
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> cmds[i].name;
        int i1, i2, i3, time;
        scanf("%d:%d:%d", &i1, &i2, &i3);
        time = i1 * 60 * 60 + i2 * 60 + i3;
        string ope;
        cin >> cmds[i].ope;
        cmds[i].time = time;
    }
    sort(cmds, cmds + n);
    int maxx = 0;
    for (int i = 0; i < n - 1; i++)
    {
        if (!(cmds[i].ope[0] == 'i' && cmds[i + 1].ope[0] == 'o' && cmds[i].time < cmds[i + 1].time))
            continue;
        mp[cmds[i].name] += cmds[i + 1].time - cmds[i].time;
        a[cmds[i].time]++;
        a[cmds[i + 1].time]--;
        maxx = max(maxx, mp[cmds[i].name]);
    }
    for (int i = 1; i < maxn; i++)
    {
        a[i] += a[i - 1];
    }
    for (int i = 0; i < m; i++)
    {
        int i1, i2, i3, time;
        scanf("%d:%d:%d", &i1, &i2, &i3);
        time = i1 * 60 * 60 + i2 * 60 + i3;
        cout << a[time] << endl;
    }

    for (auto iter = mp.begin(); iter != mp.end(); iter++)
    {
        if (iter->second == maxx)
        {
            cout << iter->first << " ";
        }
    }
    int t1 = maxx / 60 / 60, t2 = maxx % 3600 / 60, t3 = maxx % 60;
    printf("%02d:%02d:%02d", t1, t2, t3);
    return 0;
}



发表于 2020-07-03 18:47:28 回复(0)
//欢迎参观鄙人的博客:https://blog.csdn.net/qq_33375598/article/details/88018228
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
using namespace std;

const int maxn = 10010;
struct Car
{
  char id[8];     //车牌
  int time;       //记录的时刻以s为单位
  char status[4]; //in或out
}all[maxn],vaild[maxn];//all为所有记录, vaild为有效记录

int num = 0; //有效记录条数
map<string, int> parkTime; //车牌号->总时间

int timeToint(int hh, int mm, int ss){
  return hh * 3600 + mm * 60 + ss;
}

bool cmpByIdAndTime(Car a, Car b){//先车牌按字典序排列,再按时间从小到大
  int s = strcmp(a.id, b.id);
  if(s) return s < 0;
  else return a.time < b.time;
}

bool cmpByTime(Car a, Car b){//按时间从小到大
  return a.time < b.time;
}

int main(int argc, char const *argv[])
{
  int n ,k ,hh, mm, ss;
  scanf("%d%d", &n, &k);     //记录数,查询数
  for (int i = 0; i < n; ++i)
    {
      scanf("%s %d:%d:%d %s", all[i].id, &hh, &mm, &ss, all[i].status);
      all[i].time = timeToint(hh, mm, ss);
    }  

    sort(all, all + n, cmpByIdAndTime);//按车牌号和时间排序

    int maxTime = -1; //总停留时间
    for (int i = 0; i < n - 1; ++i)
     {
       if( !strcmp(all[i].id, all[i + 1].id) && //i和i+1是同一辆车
        !strcmp(all[i].status, "in") && !strcmp(all[i + 1].status,"out")){//i记录是in,i+1是out
          vaild[num++] = all[i];
          vaild[num++] = all[i + 1];
          int inTime = all[i + 1].time - all[i].time;
          if(parkTime.count(all[i].id) == 0){//map.count(Key)返回值为1或者0,1返回存在,0返回不存在,返回的是布尔类型的值
            parkTime[all[i].id] = 0;     //map中还没有这个车牌号置0
          } 
          parkTime[all[i].id] += inTime;                //  增加该车牌号的总停留时间
          maxTime = max(maxTime, parkTime[all[i].id]); //更新最大停留时间
       }
     } 

     sort(vaild, vaild + num, cmpByTime);//把有效记录按时间排序

     //now指向不超过当前查询时间的记录,numCar为当前校园内车辆
     int now = 0, numCar = 0;
    for (int i = 0; i < k; ++i)
    {
      scanf("%d:%d:%d", &hh, &mm, &ss);
      int time = timeToint(hh, mm, ss);
      while(now < num && vaild[now].time <= time){
        if(!strcmp(vaild[now].status, "in")) numCar++;
        else numCar--;
        now++;
      }
      printf("%d\n", numCar);
    }

    map<string, int>::iterator it ;//遍历所有车牌号
    for (it = parkTime.begin(); it != parkTime.end() ; ++it)
    {
      if(it->second == maxTime){//输出所有最长总停留时间的车牌
        printf("%s ", it->first.c_str());//c_str()函数返回一个指向正规C字符串的指针常量, 内容与本string串相同. 
      }
    }
//输出最长总停留时间
printf("%02d:%02d:%02d\n", maxTime / 3600, maxTime % 3600 / 60, maxTime % 60);
  return 0;
}


编辑于 2019-02-28 21:09:15 回复(0)
这个测试用例都没人发现有问题吗
发表于 2018-09-27 18:07:32 回复(5)
//
// Created by 江左 on 2021/2/19.
//

/// 给你若干车辆进出大学的记录,然后问你在指定时间内,学校内有多少车辆,最后输出今天停泊时间最大的车信息

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
using namespace std;
//一天有24*60*60秒
int arr[86400]={0};//每秒钟校园内有多少辆车
class records{
public:
    int second;
    bool status=false;
};
class car{
public:
    int sum=0;
    vector<records> v;//一天的记录
};
bool cmp(records a,records b){
    return a.second<b.second;
}
int main() {
    int n,k,sum;vector<string> longId;cin>>n>>k;
    map<string,car> map;
    for (int i = 0; i < n; ++i) {
        string id,status;int hour,min,sec;
        cin>>id;
        scanf("%d:%d:%d",&hour,&min,&sec);
        cin>>status;
        records r;
        if(status=="in") r.status= true;
        r.second=hour*60*60+min*60+sec;
        map[id].v.push_back(r);
    }
    for (auto it=map.begin();it!=map.end();it++) {
        sort(it->second.v.begin(),it->second.v.end(),cmp);//排序
        for (int i = 0; i < it->second.v.size();) {
            //连续找两个记录,一进一出
            if(i+1<it->second.v.size()){
                if(it->second.v[i].status&&!it->second.v[i+1].status){
                    int start=it->second.v[i].second;
                    int end=it->second.v[i+1].second;
                    it->second.sum+=(end-start);
                    for (int j = start; j <end ; ++j) {
                        arr[j]++;
                    }
                    i+=2;
                }else i++;
            }else break;
        }
        if(it->second.sum>sum) {//找最大sum
            longId.clear();
            sum=it->second.sum;
            longId.push_back(it->first);
        }else if(it->second.sum==sum){
            longId.push_back(it->first);
        }
    }
    for(int i=0;i<k;i++){
        int hour,min,sec;scanf("%d:%d:%d",&hour,&min,&sec);
        int second=hour*60*60+min*60+sec;
        cout<<arr[second]<<endl;
    }
    for (int i = 0; i < longId.size(); ++i) {
        cout<<longId[i]<<" ";
    }
    printf("%02d:%02d:%02d", sum / 3600, (sum % 3600) / 60, sum % 60);
    return 0;
}

发表于 2021-02-20 00:58:45 回复(0)
  • 记录车进入的时间和停留的时间,通过此可以得到在查询时刻有多少车停在校园内
  • 使用map记录每辆车在校园停留的总体时间,同时得到车停留的最大值
  • 读题的时候注意求的是每辆车停留的总体时间
  • 知识点是map,sort快排
#include<iostream>
#include<algorithm>
#include<string>
#include<map>

using namespace std;
struct Node
{
	string id;
	int time;
	int parkTime; 
	int type;
};

vector<Node>V,carIn;
int N,K;

bool cmp1(Node a,Node b)
{
	if(a.id != b.id) return a.id.compare(b.id)<0;
	else return a.time<b.time;
}

bool cmp2(Node a,Node b)
{
	return a.time<b.time;
}

int main()
{
	cin>>N>>K;
	V.resize(N);
	
	int hh,mm,ss;
	char c;
	string tmpType,id;
	for(int i = 0;i<N;i++)
	{
		cin>>id>>hh>>c>>mm>>c>>ss>>tmpType;
		int time = hh*3600 + mm*60 + ss;
		V[i].id= id;
		V[i].time = time;
		if(tmpType == "in") V[i].type = 1;
		else V[i].type = -1;
	}
	
	//
	sort(V.begin(),V.end(),cmp1);
	
	map<string,int>carName; 
	//同时将map carName初始化,避免未初始化错误 
	for(int i=0;i<N;i++)
		carName[V[i].id] = 0;
	 
	//计算停留时间,同时得到总停留时间,使用map保存 
	int MaxParkTime = 0;
	for(int i = 0;i<N-1 ;i++)
	{
		if(V[i].id== V[i+1].id && V[i].type == 1 && V[i+1].type == -1)
		{
			int time = V[i+1].time - V[i].time;
			V[i].parkTime = time;
			carIn.push_back(V[i]);
			carName[V[i].id] += time;
			if(MaxParkTime < carName[V[i].id])
				MaxParkTime = carName[V[i].id]; 
		}
			
	}
	
	//按照进入时间的早晚排序
	sort(carIn.begin(),carIn.end(),cmp2);
	
	//查询
	for(int i = 0;i<K;i++)
	{
		cin>>hh>>c>>mm>>c>>ss;
		int time = hh*3600 + mm*60 + ss;
		
		int cnt = 0;
		for(int j = 0;j<carIn.size();j++)
		{
			if(carIn[j].time <= time && (carIn[j].time + carIn[j].parkTime)>time)
				cnt++;	
		}
		cout<<cnt<<endl; 
	} 
	
	for(map<string,int>::iterator it = carName.begin();it!=carName.end();it++)
	{
		if(it->second == MaxParkTime)
			cout<<it->first<<" ";
	}
	
	printf("%02d:%02d:%02d",MaxParkTime/3600,(MaxParkTime%3600)/60,MaxParkTime%60);
	
	return 0;
}

发表于 2020-10-13 20:40:50 回复(0)
没用map的一种解法:
#include<stdio.h>
(737)#include<math.h>
#include<algorithm>
(831)#include<cstring>
using namespace std;
 

struct record{
	
	char name[25]; //车牌号 	
	int hour;  //通话开始/结束时间 
	int minute;
	int sec; 
	int abtime; 
	bool status;	//车辆状态,进入or退出 

}cr[40100];

struct parkcar{
	
	char num[25]; //车牌号
	int st; //进入时间 
	int et; //离开时间
	int du;//持续时间 
	//以上均为绝对时间 
}pc[40100];

bool cmp(record a,record b){ //原始记录排序 

	if(strcmp(a.name,b.name)) return strcmp(a.name,b.name)<0;
	else {
		
		if(a.hour!=b.hour) return a.hour<b.hour;
		else{
			if(a.minute!=b.minute)return a.minute<b.minute;
			else {
				return a.sec<b.sec;
			} 
		}
	}
} 

bool cmp2(parkcar a,parkcar b){//按入场时间排序。早的在前 
	if(a.st!=b.st) return a.st<b.st;
	else {
		return a.du>b.du;
	}
}

bool cmp3(parkcar a,parkcar b){//按字母序排序 
	return strcmp(a.num,b.num)<0;
}

bool cmp4(parkcar a,parkcar b){ //按持续时间排序 
	if(a.du!=b.du) return a.du>b.du; 
	else return strcmp(a.num,b.num)<0;
}

void count(int h,int m,int s,int &abt);

int pnum[40100]; //记录停车时间最长的车号

int mt = 0;//记录停车最长时间 

int main(){
	
	//freopen("in.txt","r",stdin);
	
	memset(pnum,-1,sizeof(pnum));
	
	int n = 0;
	scanf("%d",&n); //停车记录总数 
	
	int k=0;
	scanf("%d",&k); //查询总数
	 
	int sn = n;
	 
	//停车记录输入过程 
	while(n--){

		scanf("%s %d:%d:%d",cr[n].name,&cr[n].hour,&cr[n].minute,&cr[n].sec);
		char s[10];
		scanf("%s",s);
		if(strcmp(s,"out")) cr[n].status = 1;
		else cr[n].status = 0;
		
		count(cr[n].hour,cr[n].minute,cr[n].sec,cr[n].abtime);
		//算出对应的绝对时间 
	} 
	
	
	//按时间排序过程 
	
	sort(cr,cr+sn,cmp); //排序函数 
	

	//记录匹配 

	int car=0;
	int l = 0;
	for(int i=1;i<sn;++i){
		
		//若前后记录同属一车 
		if(!(strcmp(cr[i-1].name,cr[i].name))){

			if(cr[i-1].status){//当前记录是开始状态 
				if(cr[i].status){//下一条记录是开始状态,匹配失败 
					continue;
				}
				else{//下一条记录是挂断状态,匹配成功 				
					strcpy(pc[car].num,cr[i].name);
					pc[car].st = cr[i-1].abtime;
					pc[car].et = cr[i].abtime;
					pc[car].du = pc[car].et - pc[car].st;					
					
					++car;
					
				}
								
			}
			
		}	
			
	}
	
	
	//有效记录按开始时间排序 
	sort(pc,pc+car,cmp2); //排序函数 
	
	
	//查询输入与处理
	for(int i=0;i<k;++i){ 
		int r = 0;
		int h,m,s,abt;
		scanf("%d:%d:%d",&h,&m,&s);
		count(h,m,s,abt);
		for(int j=0;j<car;++j){//每个查询一个循环
			
			if(abt>=pc[j].st){
				if(abt<pc[j].et)
				++r;
				
			}			
			else break;
		
		}
		printf("%d\n",r);
		
	} 
	
	
	//有效记录按车牌号排序
	sort(pc,pc+car,cmp3); //排序函数
	
	//求累积时间 
	for(int i=1;i<car;++i){
		
		if(!strcmp(pc[i].num,pc[i-1].num)) 
		{
			int j=i+1;
			pc[i].du +=pc[i-1].du;
			while(!strcmp(pc[i].num,pc[j].num)){
				pc[i].du+=pc[j].du;
				j++;
			}
			
			i=j;
		}
		
	}

	//最长泊车时间和对应车牌号输出
	sort(pc,pc+car,cmp4); //排序函数
	mt = pc[0].du;
	
	for(int i=0;i<car;++i){
		
		if(pc[i].du==mt)printf("%s ",pc[i].num);
		else break;
		
		
}
	
	int h = mt/3600;
	mt -=h*3600;
	int m = mt/60;
	mt -=m*60;
	int s = mt;
	
	printf("%02d:%02d:%02d",h,m,s);

	return 0;
} 

void count(int h,int m,int s,int &abt){//绝对时间换算 
	abt = h*3600 + m*60 +s;
}


发表于 2020-03-25 20:30:27 回复(0)
牛客上过不了,pta上有一个超时,有人看麻烦回复我哪里能改正
def time(x):
    return int(x[0:2]) * 3600 + int(x[3:5]) * 60 + int(x[6:8])

def main():
    a = list(map(int,input().split()))
    d,e,m,q,s = {},{},[],0,{}
    n = sorted([input().split() for i in range(a[0])],key = lambda x:x[1])
    p = [input() for i in range(a[1])]
    for i in n:
        if i[2] == 'in':
            e[i[0]] = i[1]
        elif i[0] in e:
            try:
                d[i[0]] += time(i[1]) - time(e[i[0]])
            except:
                d[i[0]] = time(i[1]) - time(e[i[0]])
            m.extend([[i[0],e[i[0]],1],i[0:2] + [0]])
            del e[i[0]]

    for i in sorted(m,key = lambda x:x[1]):
        while p and i[1] > p[0]:
            print(len(s))
            del p[0]
        if i[2]:
            s[i[0]] = i[1]
        else:
            del s[i[0]]
    for i in p:
        print(0)

    for i in d:
        if d[i] > q:
            r,q = [i],d[i]
        elif d[i] == q:
            r.append(i)

    q1,q = divmod(q,3600)
    q2,q = divmod(q,60)
    print(' '.join(sorted(r)),'{:02}:{:02}:{:02}'.format(q1,q2,q))
main()


编辑于 2020-02-29 19:23:51 回复(0)
这边直接超时,PTA那边也有1个超时。感觉已经是比较省时间的了。用了map来存每个车对应的停留时间,用一个24*60*60的数组来存每个时间对应的学校里面的车数,然后这里不用每个时刻都都赋值,只用赋值对应车进出的时间,记住这里出现每个车(无论其进出是否有效,无效的直接就等于前一个时间点停留的数目就行了,因为后续要遍历,不然会出错)。后面查询的时候对M个记录进行遍历,然后找出这个时间点在那两条记录之间,就输出对应的值。利用查询时间是升序排列的,可以用 一个index来存储上一次遍历的下标。
#include<iostream>
(720)#include<map>
#include<vector>
(721)#include<string>
#include<cstring>
(803)#include<algorithm>
using namespace std;
const int MAXN = 10001;
const int MAXT= 864001;
struct car {
	string carNo;
	int time;
	string states;
	car(string s, int time, string states) :carNo(s), time(time), states(states) {}
};
vector<car>carInfo;
vector<string>resultNo;
map<string, int>myMap;//用来保存每个车对应的停留时间,因为一个车逗留时间不止一次,所以需要记录下来
int TimeofCar[MAXT];//每个时间对应的车辆数目。
int longestTime = 0;
bool isOutTrue[MAXN];
/*int str2time(string s) {
	//int hours = stoi(s.substr(0, 2), 0, 10);
	//int minutes = stoi(s.substr(3, 2), 0, 10);
	//int seconds = stoi(s.substr(6, 2), 0, 10);
	string h = s.substr(0, 2);
	string m = s.substr(3, 2);
	string sec = s.substr(6, 2);
	int hours = (h[0] - '0') * 10 + h[1] - '0';
	int minutes = (m[0] - '0') * 10 + m[1] - '0';
	int seconds = (sec[0] - '0') * 10 + sec[1] - '0';
	
	return hours * 3600 + minutes * 60 + seconds;
}*/
bool compare(car c1, car c2) {
	return c1.time < c2.time;
}
bool comp(string s1, string s2) {
	int t = strcmp(s1.c_str(), s2.c_str());
	if (t==1) {//s1>s2
		return false;
	 }
	else{      //s1<=s2
		return true;
	}
}
int main() {
	//freopen("C:\\Users\\47\\Desktop\\1.txt", "r", stdin);
	fill(TimeofCar, TimeofCar + MAXN, 0);
	fill(isOutTrue, isOutTrue + MAXN, false);
	int M, N;
	cin >> M >> N;
	for (int i = 0; i < M; i++) {
		string carNo,states;
		int hour,minute,second;
		cin >> carNo;
		scanf("%d:%d:%d", &hour, &minute, &second);
		cin>> states;
		carInfo.push_back(car(carNo,3600*hour+60*minute+second, states));
	}
	sort(carInfo.begin(),carInfo.end(),compare);
	int preNum = 0;
	for (int i = 0; i < M; i++) {
		int tt = carInfo[i].time;
		if (carInfo[i].states == "out" && isOutTrue[i]&&i!=M-1) {
			TimeofCar[tt]=--preNum;
		}
		else if (carInfo[i].states == "out" && !isOutTrue[i]&&i!=M-1) {
				TimeofCar[tt] = preNum;
		}
		else if (carInfo[i].states == "out" &&isOutTrue[i]&&i == M - 1) {//末尾处理
				TimeofCar[tt] = --preNum;
		}
		else if (carInfo[i].states == "out" &&!isOutTrue[i] && i == M - 1) {//末尾处理
				TimeofCar[tt] = preNum;
		}
		else if (i == M - 1) {//最后一条为in,肯定错误
				TimeofCar[tt] = preNum;
		}
		//  in且不为最后一条的的情况
		else {
			int j = i + 1;
			for (; j < M; j++) {
				if (carInfo[i].carNo == carInfo[j].carNo && carInfo[j].states == "in") {//无效
						TimeofCar[tt] = preNum;
					break;
				}
				else if (carInfo[i].carNo == carInfo[j].carNo && carInfo[j].states == "out") {//有效
						TimeofCar[tt] = ++preNum;
					int temp = carInfo[j].time - tt;
						myMap[carInfo[i].carNo] += temp;
						temp = myMap[carInfo[i].carNo];
					if (temp > longestTime) {
						longestTime = temp;
						resultNo.clear();
						resultNo.push_back(carInfo[i].carNo);
					}
					else if (temp == longestTime) {
						resultNo.push_back(carInfo[i].carNo);
					}
					isOutTrue[j] = true;
					break;
				}
			}
			if (j == M) {
				TimeofCar[tt] = preNum;
			}
		}
	}
	int index = 0;//ascend,存着
	while (N--) {
		int time;
		int hour, minute, second;
		scanf("%d:%d:%d", &hour, &minute, &second);
		time = 3600 * hour + 60 * minute + second;
		int result=0;
		for (int i = index; i < M; i++) {
			int ti = carInfo[i].time;
			int ti_1 = carInfo[i + 1].time;
			if (i!=M-1&&time >= ti && time < ti_1) {
				result = TimeofCar[ti];
				index = i;
				break;
			}
			if (i == M - 1) {
				result = TimeofCar[ti];
				index = i;
				break;
			}
		}
		printf("%d\n",result);
	}
	sort(resultNo.begin(),resultNo.end(),comp);
	for (int i = 0; i < resultNo.size(); i++) {
		cout << resultNo[i] << " ";
	}
	printf("%02d:%02d:%02d", longestTime / 3600, (longestTime % 3600) / 60, longestTime % 60);
}

发表于 2020-02-23 22:40:01 回复(0)

import java.util.*;

public class Main {

     static int n = 0;
     static int k = 0;
     static List<CarInfo> carArr = new ArrayList();
     static int[] timerArr;
     static int[] day= new int[60 * 60 * 24];
     static HashMap<String,Integer> result = new HashMap<>();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();
        timerArr = new int[k];

        Arrays.fill(day,0);

        for (int i = 0; i < n; i++) {
            String name = sc.next();
            String timeStr = sc.next();
            String enterStr = sc.next();
            CarInfo carInfo = new CarInfo(name,second(timeStr),(enterStr.equals("in") ? 0:1));
            carArr.add(carInfo);
        }



        for (int i = 0; i < k; i++) {

            String time = sc.next();

            timerArr[i] = second(time);
        }

        int maxTime = 0;

        Collections.sort(carArr);

        for (int i = 1 ; i < carArr.size(); i ++){

            CarInfo carInfo1 = carArr.get(i - 1);
            CarInfo carInfo2 = carArr.get(i);
            if(carInfo1.enter == 0 && carInfo2.enter == 1 && carInfo2.name.equals(carInfo2.name)){
                if(result.get(carInfo1.name) == null){
                    result.put(carInfo1.name,0);
                }

                int allTime = result.get(carInfo1.name) + (carInfo2.time - carInfo1.time);
                result.put(carInfo1.name,allTime);
                if(allTime > maxTime){
                    maxTime = allTime;
                }

                day[carInfo1.time] ++ ;
                day[carInfo2.time] -- ;

            }
        }

        for(int i = 0 ; i < timerArr.length; i ++){

            int num = 0;

            int second = timerArr[i];

            for(int j = 0 ; j <= second ; j ++){
                 num += day[j];

            }

            System.out.println(num);
        }

        for (String key: result.keySet()) {

            if(result.get(key) == maxTime){
                System.out.print(key + " ");
            }
        }

        int h = maxTime/60/60;
        int m = (maxTime - h * 60 * 60 )/60;
        int s = (maxTime - h * 60 * 60 - m * 60 )%60;

        System.out.printf("%02d:%02d:%02d",h,m,s);



    }


    static int second (String timeStr){

        String[] a = timeStr.split(":");

        return (Integer.parseInt(a[0])) * 60 * 60 + (Integer.parseInt(a[1])) * 60 + (Integer.parseInt(a[2]));

    }




    public static class CarInfo implements Comparable<CarInfo>{
        int time;
        int enter;
        String name;

        public CarInfo(String name, int time , int enter){
            this.name = name;
            this.enter = enter;
            this.time = time;
        }


        @Override
        public int compareTo(CarInfo o) {
            if(this.name.compareTo(o.name) == 0){
                return this.time >= o.time?1:-1;
            }
            return this.name.compareTo(o.name);
        }
    }


}




case能过,提交java一直卡在34行,不是特别懂。 - -


编辑于 2020-01-10 11:27:46 回复(0)
不知为何,只要开24*60*60的数组就会跳段错误,改成记录进出时间的数组就过了
#include <iostream>
#include <string>
#include<algorithm>
using namespace std;
struct park{
    string name;
    int hh;
    int mm;
    int ss;
    bool type;
    bool operator < (const park& t) const{
        if(name!=t.name) return name<t.name;
        return (hh<t.hh)||(hh==t.hh&&mm<t.mm)||(hh==t.hh&&mm==t.mm&&ss<t.ss);
    }
};
int main()
{
    int n,m;
    cin>>n>>m;
    park num[n];
    for(int i=0;i<n;i++){
        string s1,s2,s3;
        cin>>s1>>s2>>s3;
        num[i].name =s1;
        num[i].hh =(s2[0]-'0')*10+s2[1]-'0';
        num[i].mm =(s2[3]-'0')*10+s2[4]-'0';
        num[i].ss =(s2[6]-'0')*10+s2[7]-'0';
        num[i].type =(s3=="in");
    }
    sort(num,num+n);
    int cnt[n];
    for(int i=0;i<n;i++)
        cnt[i]=0;
    int i=0,c=0,ii=0;
    string a[n];
    int b[n];
    while(i<n-1){
        string s =num[i].name;
        a[c]=s;
        int j=0;
        while(i<n-1&&s==num[i].name&&s==num[i+1].name){
            if(!num[i].type) {
                i++;
                continue;
            }
            if(num[i+1].type){
                i++;
                continue;
            }
            cnt[ii]=num[i].hh*60*60+num[i].mm*60+num[i].ss;
            cnt[ii+1]=num[i+1].hh*60*60+num[i+1].mm*60+num[i+1].ss;
            ii+=2;
            j +=((num[i+1].hh*60*60+num[i+1].mm*60+num[i+1].ss)-(num[i].hh*60*60+num[i].mm*60+num[i].ss));
            i+=2;
        }
        if(i<n-1&&s==num[i].name) i++;
        b[c]=j;
        c++;
    }
    for(i=0;i<m;i++){
        string s;
        cin>>s;
        int x=((s[0]-'0')*10+s[1]-'0')*3600+((s[3]-'0')*10+s[4]-'0')*60+((s[6]-'0')*10+s[7]-'0');
        int y=0;
        for(int j=0;j<ii;j+=2)
            if(x>=cnt[j]&&x<cnt[j+1])
            y++;
        cout<<y<<endl;
    }
    int mtime =0;
    for(i=1;i<c;i++)
        if(b[i]>b[mtime])
        mtime =i;
    for(i=0;i<c;i++)
        if(b[i]==b[mtime])
        cout<<a[i]<<" ";
    cout<<b[mtime]/3600/10<<b[mtime]/3600%10<<":"<<b[mtime]/60%60/10<<b[mtime]/60%60%10<<":"<<b[mtime]%60/10<<b[mtime]%60%10<<endl;
    return 0;
}


发表于 2020-01-10 02:10:00 回复(0)
使用record结构存储记录;
将记录按照时间排序;
遍历记录,遇到in记录就插入map,遇到out记录就和map中的in记录组成一对,并在num数组中做记号。
num数组记录着每一秒的来车、去车信息,将其从开始处求和即可求出每一秒的车数。
利用另一个map记录每辆车的车牌和总停留时间。
最后用迭代器遍历第二个map,将停留时间最长的输出。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;

struct record
{
	string plate,status;
	int time;
};

int N,K,num[86400]={0},maxtime=0;
//N为记录数,K为查询次数,num[]记录每个时间点的车数变化并最后生成每个时间点的车数
record r[10000];//r[]记录所有记录
map<string,int>campus,car;//campus存储进校的车和进校时间,car存储所有的车及其总时间

bool Comp(record x,record y)
{	return x.time<y.time;
}

int main()
{
	char c;
	int hh,mm,ss;
	map<string,int>::iterator it1,it2;
	cin>>N>>K;
	for(int i=0;i<N;i++){
		cin>>r[i].plate>>hh>>c>>mm>>c>>ss>>r[i].status;
		r[i].time=hh*3600+mm*60+ss;
		if(car.find(r[i].plate)==car.end()){//若car中没有该车,将其加入
			car[r[i].plate]=0;
		}
	}
	sort(r,r+N,Comp);//将所有记录按照时间顺序排序
	for(int i=0;i<N;i++){//遍历所有记录
		if(r[i].status=="in"){//对于一条in记录,直接加入campus(若已有该车记录则会将旧记录替换)
			campus[r[i].plate]=r[i].time;
		}
		else{//对于一条out记录,查验campus中是否已有in记录
			it1=campus.find(r[i].plate);
			if(it1!=campus.end()){//若有in记录,形成in-out组合
				it2=car.find(r[i].plate);
				(it2->second)+=r[i].time-it1->second;//更新该车总时间
				if(it2->second>maxtime)maxtime=it2->second;//更新maxtime
				num[it1->second]++;//在in的时间点,num[]++
				num[r[i].time]--;//在out的时间点,num[]--
				campus.erase(it1);//在campus中消除该车记录,表示开走了
			}
		}
	}
	for(int i=1;i<86400;i++)num[i]+=num[i-1];//将num[]更新为之前车数变化的和,即现在车数
	while(K--){
		cin>>hh>>c>>mm>>c>>ss;
		cout<<num[hh*3600+mm*60+ss]<<endl;
	}
	for(it2=car.begin();it2!=car.end();++it2){
		if(it2->second==maxtime)cout<<it2->first<<' ';
	}
	printf("%02d:%02d:%02d",maxtime/3600,maxtime/60%60,maxtime%60);
}


编辑于 2020-01-08 15:40:19 回复(0)
本人是个喜欢用C++来解题的人,用到C++的话就会无意中使用到一种模块化的思路来接替,这样子思路会很清晰。虽然代码不够短,但是思路够清晰,同时也容易发现错误。下面分享下我的代码。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <iomanip>
using namespace std;
//用来将**:**:**格式的时间和按秒的时间进行转换
class Time
{
public:
    Time();
    Time(int seconds);
    friend istream& operator>> (istream& input, Time& t);
    friend ostream& operator<< (ostream& output, Time& t);
    friend bool operator<(const Time& t1, const Time& t2);
    friend int operator- (const Time& t1, const Time& t2);
    int getSeconds()const;
private:
    int seconds;
};
//表示一条记录
struct Record
{
    string plate_number;
    Time t;
    int in_out;
};
map<string, int> plateNumber_to_totolTime_map; //车牌号到一共停留的总时间
map<Time, int> time_to_totalCarNumber_map; //记录了某个时刻时一共有多少辆车在学校里
bool comp1(const Record& r1, const Record& r2);  //这个排序函数是用来将数组里相同车牌的放到一块,方便删除无效的记录
bool comp2(const Record& r1, const Record& r2);  //这个排序函数是用来对数组的记录进行按时间的排序,方便我统计某个时刻有多少辆车
void RemoveWrongItems(const vector<Record>& rawRecords, vector<Record>& records); //删除无效的记录
void solveTotalCarNumber(vector<Record>& records); //用来填充time_to_totalCarNumber_map:某时刻有多少辆车停留在学校
void query(int k); //将查询那部分代码抽出来,弄成一个函数
void findLongestStayCars(); //找到停留时间最长的车辆
int main()
{
    int n, k;
    cin >> n >> k;
    vector<Record> rawRecords; //这个数组既包含有效的记录,也包含无效的记录
    for (int i = 0; i < n; i++) //for循环用来读入数据,填充rawRecords
    {
        Record record;
        string in_out_str;
        cin >> record.plate_number >> record.t >> in_out_str;
        record.in_out = (in_out_str == "in" ? 1 : -1);
        rawRecords.push_back(record);
    }
    sort(rawRecords.begin(), rawRecords.end(), comp1); //排序使得相同车牌的记录放到一起,方便我删除无效的记录
    vector<Record> records; //用来记录有效的记录
    RemoveWrongItems(rawRecords, records); //删除无效的记录
    sort(records.begin(), records.end(), comp2); //现在留下的都是有效的记录了,这个排序的目的是让数组按时间排序
    solveTotalCarNumber(records); //填充time_to_totalCarNumber_map,来解决某个时刻有多少辆车的问题
    query(k); //接受查询,并给出回答
    findLongestStayCars(); //求出停留时间最长的车辆
    return 0;
}

//Time definition
Time::Time()
{
    seconds = 0;
}
Time::Time(int seconds)
{
    this->seconds = seconds;
}
istream& operator>> (istream& input, Time& t)
{
    int h, m, s;
    input >> h;
    input.ignore();
    input >> m;
    input.ignore();
    input >> s;
    t.seconds = h * 3600 + m * 60 + s;
    return input;
}
ostream& operator<< (ostream& output, Time& t)
{
    int h, m, s;
    h = t.seconds / 3600;
    m = t.seconds % 3600 / 60;
    s = t.seconds % 60;

    output << setfill('0') << setw(2) << h << ":"
        << setfill('0') << setw(2) << m << ":"
        << setfill('0') << setw(2) << s;
    return output;
}
bool operator<(const Time& t1, const Time& t2)
{
    return t1.seconds < t2.seconds;
}
int operator- (const Time& t1, const Time& t2)
{
    return t1.seconds - t2.seconds;
}
int Time::getSeconds()const
{
    return seconds;
}

bool comp1(const Record& r1, const Record& r2)
{
    if (r1.plate_number != r2.plate_number)
    {
        return r1.plate_number < r2.plate_number;
    }
    else
    {
        return r1.t < r2.t;
    }
}
void RemoveWrongItems(const vector<Record>& rawRecords, vector<Record>& records)
{
    int startIndex = 0, endIndex = 0;
    while (1)
    {
        for (; endIndex != rawRecords.size() - 1; endIndex++)
        {
            if (rawRecords[endIndex].plate_number != rawRecords[endIndex + 1].plate_number)
            {
                break;
            }
        }
        for (int i = startIndex; i < endIndex;)
        {
            if (rawRecords[i].in_out == 1 && rawRecords[i + 1].in_out == -1)
            {
                records.push_back(rawRecords[i]);
                records.push_back(rawRecords[i + 1]);
                const string& plate_number = rawRecords[i].plate_number;
                int diff_time = rawRecords[i + 1].t - rawRecords[i].t;
                plateNumber_to_totolTime_map[plate_number] += diff_time;
                i += 2;
            }
            else
            {
                i++;
            }
        }
        if (endIndex == rawRecords.size() - 1)
        {
            break;
        }
        else
        {
            startIndex = endIndex + 1;
            endIndex = startIndex;
        }

    }
}
bool comp2(const Record& r1, const Record& r2)
{
    return r1.t < r2.t;
}
void solveTotalCarNumber(vector<Record>& records)
{
    int totalCarNumber = 0;
    for(int i = 0;i < records.size();i++)
    {
        totalCarNumber += records[i].in_out;
        time_to_totalCarNumber_map[records[i].t] = totalCarNumber;
    }
}
void query(int k)
{
    for (int i = 0; i < k; i++)
    {
        Time temT;
        cin >> temT;
        int ans = 0;
        auto it = time_to_totalCarNumber_map.lower_bound(temT);
        if (it->first.getSeconds() > temT.getSeconds())
        {
            if (it != time_to_totalCarNumber_map.begin())
            {
                it--;
                ans = it->second;
            }
            else
            {
                ans = 0;
            }
        }
        else
        {
            ans = it->second;
        }
        cout << ans << endl;
    }
}
void findLongestStayCars()
{
    int longestTime = 0;
    vector<string> cars;
    for (auto it : plateNumber_to_totolTime_map)
    {
        if (it.second > longestTime)
        {
            longestTime = it.second;
            cars.clear();
            cars.push_back(it.first);
        }
        else if(it.second == longestTime)
        {
            cars.push_back(it.first);
        }
    }
    for (auto it : cars)
    {
        cout << it << " ";
    }
    Time temT(longestTime);
    cout << temT << endl;
}
发表于 2019-12-06 20:49:10 回复(0)
#include <iostream>
#include <vector>
#include <map>
#include <string.h>
#include <utility>

using namespace std;

const int dayTime = 24 * 60 * 60 + 1;
int parkingRec[dayTime];

int timeConverter(string t);
string timeConverter(int t);
int lowbit(int n);
int getSum(int i);
void update(int index, int val);

int main() {

    int N, K;
    cin >> N >> K;
    int identity = 0;
    map<string, int> plt2int;    // car plate mapping to integer
    string int2plt[N];

    map<string, string> parkingLog[N];  // 成员为map的数据类型数组

    string plt, ts, sta;
    for (int i = 0; i < N; i++) {
        cin >> plt >> ts >> sta;
        if (!plt2int.count(plt)) {
            // firstly complete the mapping job
            plt2int.insert({plt, identity});
            int2plt[identity] = plt;
            identity++;
        }

        // then put the parking record in parkingLog
        parkingLog[plt2int[plt]].insert({ts, sta});
    }

    // map本身会通过主键进行升序排序,该循环用来过滤parkingLog数据结构中中的invalid的停车记录
    for(int i = 0; i < identity; i++) {
        auto iter = parkingLog[i].begin();
        while((iter != parkingLog[i].end()) && (next(iter) != parkingLog[i].end())) {
            if (iter->second == "in") {
                if(next(iter)->second == "in") {
                    iter = parkingLog[i].erase(iter);
                } else { iter++; iter++; }
            } else { iter = parkingLog[i].erase(iter); }
        }
        if(iter != parkingLog[i].end()) parkingLog[i].erase(iter);
    }
  
    int parking_time[identity]; //用于记录每辆车的total_parking_time,数组下标即为即为车辆的数组identity
    for(int i = 0; i < identity; i++) {
        auto iter = parkingLog[i].begin(), end = parkingLog[i].end();
        int total_parking_time = 0;
        while(iter != end) {
            string in_time = iter->first, out_time = next(iter)->first;
            int in_time_i = timeConverter(in_time), out_time_i = timeConverter(out_time);
            update(in_time_i, 1);
            update(out_time_i, -1);
            total_parking_time +=  out_time_i - in_time_i;
            iter++;iter++;
        }
        parking_time[i] = total_parking_time;
    }

    for (int i = 0; i < K; i++) {
        string check_time;
        cin >> check_time;
        cout << getSum(timeConverter(check_time)) << endl;
    }

    int max_parking_time = 0;
    vector<string> m_car;
    for (int i = 0; i < identity; i++)
        if (parking_time[i] > max_parking_time)
            max_parking_time = parking_time[i];
    for (int i = 0; i < identity; i++)
        if (parking_time[i] == max_parking_time)
            m_car.push_back(int2plt[i]);

    for (auto &plt : m_car)
        cout << plt << " ";
    cout << timeConverter(max_parking_time) << endl;

}

int timeConverter(string t) {
    if (t == "") return 0;
    int hour = stoi(t.substr(0, 2));
    int min = stoi(t.substr(3, 5));
    int sec = stoi(t.substr(6, 8));

    return sec + min * 60 + hour * 60 * 60;
}

string timeConverter(int t) {
    int sec = t % 60;
    int min = (t/60) % 60;
    int hour = t/3600;

    string s, m, h;
    if ((sec/10) == 0) s = "0" + to_string(sec); else s = to_string(sec);
    if ((min/10) == 0) m = "0" + to_string(min); else m = to_string(min);
    if ((hour/10) == 0) h = "0" + to_string(hour); else h = to_string(hour);

    return h + ":" + m + ":" + s;
}

int lowbit(int n) {
    return n & -n;
}

void update(int index, int val) {
    while (index < dayTime) {
        parkingRec[index] += val;
        index += lowbit(index);
    }
}

int getSum(int index) {
    int sum = 0;
    while (index > 0) {
        sum += parkingRec[index];
        index -= lowbit(i);
    }
    return sum;
}


发表于 2019-12-01 15:28:32 回复(0)
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <vector>
# define Maxn 10001
using namespace std;

int n, k, num = 0, temp = 0;
vector<int> Max_Car;
vector<int> Valid;
struct node{
	char plate[10];
	int hh, mm, ss, time;
	bool tag;//true是in, false是out; 
}Re[Maxn];

int Cul(int h, int m, int s){
	return s+m*60+h*60*60;
}

bool cmp(node a, node b){
	if(strcmp(a.plate, b.plate) != 0)	return strcmp(a.plate, b.plate) < 0;
	else 	return a.time < b.time;
}

bool cmp_V(int a, int b){
	return Re[a].time < Re[b].time;
}

bool cmp_M(int a, int b){
	return strcmp(Re[a].plate, Re[b].plate) < 0;
}

int Query(int rear){
	if(temp == Valid.size())	return num;
	while(Re[Valid[temp]].time <= rear){
		if(Re[Valid[temp]].tag)	num++;
		else	num--;
		temp++;		if(temp == Valid.size())	break;
	} 
	return num;
}

void Cul_Time(int M){
	int h, m, s;
	s = M % 60;		M /= 60;	
	m = M % 60;		h = M / 60;
	printf("%02d:%02d:%02d\n", h, m, s);
}

int main()
{
	char str[10], tag[4];	int h, m, s, Max_Time = 0;	
	scanf("%d %d", &n, &k);
	for(int i = 0; i < n; i++){
		scanf("%s %d:%d:%d %s", Re[i].plate, &Re[i].hh, &Re[i].mm, &Re[i].ss, tag);
		Re[i].time = Cul(Re[i].hh, Re[i].mm, Re[i].ss);
		if(tag[0] == 'i')	Re[i].tag = true;
		else Re[i].tag = false;
	}
	sort(Re, Re+n, cmp);
	
	for(int i = 0; i < n-1; i++){
		while(strcmp(Re[i].plate, Re[i+1].plate) == 0){
			if(Re[i].tag && !Re[i+1].tag){
				Valid.push_back(i);	Valid.push_back(i+1);
			}
			i++;	if(i + 1 >= n)	break;
		}
	}
	
	for(int i = 0; i < Valid.size()-1; i++){
		int t = -Re[Valid[i]].time;
		while(strcmp(Re[Valid[i]].plate, Re[Valid[i+1]].plate) == 0){
			 if(Re[Valid[i+1]].tag)		t -= Re[Valid[i+1]].time;
			 else	t += Re[Valid[i+1]].time;
			 i++;	if(i+1 >= Valid.size())	break;
		}
		if(t > Max_Time){
			Max_Time = t;
			Max_Car.clear();	Max_Car.push_back(Valid[i]); 
		}
		else if(t == Max_Time)
			Max_Car.push_back(Valid[i]); 
	}
	sort(Valid.begin(), Valid.end(), cmp_V) ;

	for(int i = 0; i < k; i++){
		scanf("%d:%d:%d", &h, &m, &s);
		int rear = Cul(h, m, s);
		printf("%d\n", Query(rear));
	}
	sort(Max_Car.begin(), Max_Car.end(), cmp_M);
	for(int i = 0; i < Max_Car.size(); i++){
		printf("%s ", Re[Max_Car[i]].plate);
	}
	Cul_Time(Max_Time);
	return 0;	
}

发表于 2019-08-23 16:04:23 回复(0)
这题没说清楚,默认应该是只能先进再出,但是也有可能车是先出去,再进来的情况(车在这里待了一夜)
```
#include<bits/stdc++.h>
using namespace std;
//默认 只能先进才能出 
struct node1
{  string time;  string status;  };
struct  node2
{  string in;  string out;
};
int cmp(const node1& a,const node1& b)
{  if(a.time>b.time)  {  return 0;   }  else return 1;
}
int cmp2(const node2& a,const node2& b)
{  if(a.in>b.in)  {  return 0;  }  else return 1;
}
int main()
{  int n,k;  cin>>n>>k; 
 map<string,vector<node1> > m1;   for(int i=0;i<n;i++)  {    string plate;  string time;  string status;  cin>>plate>>time>>status;  node1 tmp;tmp.time=time;tmp.status=status;  m1[plate].push_back(tmp);     }   map<string,vector<pair<string,string> > > m2;  map<string,vector<node1> >::iterator it;  for(it=m1.begin();it!=m1.end();it++)  {  sort(it->second.begin(),it->second.end(),cmp);   int i=0;  while(i<it->second.size()-1)  {  if(it->second[i].status=="in"&&it->second[i+1].status=="out")//||it->second[i].status=="out"&&it->second[i].status=="in"  {   m2[it->first].push_back(pair<string,string>{it->second[i].time,it->second[i+1].time});   i+=2;  }   else i+=1;  }   }   vector<node2> v;  map<string,vector<pair<string,string> > >::iterator it2;   for(it2=m2.begin();it2!=m2.end();it2++)  {   for(int i=0;i<it2->second.size();i++)  {  node2 tmp;tmp.in=it2->second[i].first;tmp.out=it2->second[i].second;  v.push_back(tmp);    }  }   sort(v.begin(),v.end(),cmp2);   for(int i=0;i<k;i++)  {  int ans=0;  string q;  cin>>q;  for(int i=0;i<v.size();i++)  {  if(v[i].in<=q)  {  if(v[i].out>q)  {  ans++;  }  }  else break;  }   cout<<ans<<endl;   }  map<int,vector<string> > m3;  for(it2=m2.begin();it2!=m2.end();it2++)  {  int sum=0;  for(int i=0;i<it2->second.size();i++)  {   int h1=0,m1=0,s1=0;  int h2=0,m2=0,s2=0;   int index=0;  int show=0;    it2->second[i].first+=":";  it2->second[i].second+=":";   for(int j=0;j<it2->second[i].first.size();j++)  {   if(it2->second[i].first[j]==':')  {  int d=10;  for(int k=index;k<j;k++)   {  if(show==0)  {  h1+=d*(it2->second[i].first[k]-'0');  d/=10;  }  else  if(show==1)  {  m1+=d*(it2->second[i].first[k]-'0');  d/=10;  }  else  {   s1+=d*(it2->second[i].first[k]-'0');   d/=10;  }    }  index=j+1;  show++;  }  }    index=0,show=0;  for(int j=0;j<it2->second[i].second.size();j++)  {   if(it2->second[i].second[j]==':')  {  int d=10;  for(int k=index;k<j;k++)   {  if(show==0)  {  h2+=d*(it2->second[i].second[k]-'0');  d/=10;  }  else  if(show==1)  {  m2+=d*(it2->second[i].second[k]-'0');  d/=10;  }  else  {  s2+=d*(it2->second[i].second[k]-'0');  d/=10;  }    }  index=j+1;  show++;  }  }   sum+=((h2-h1)*3600+(m2-m1)*60+s2-s1);   }   m3[sum].push_back(it2->first);   }  map<int,vector<string> >::iterator it3 = m3.end();it3--;  for(int i=0;i<it3->second.size();i++)  cout<<it3->second[i]<<" ";  int ans2=it3->first;  int hh=ans2/3600;  ans2%=3600;  int mm=ans2/60;  ans2%=60;  int ss=ans2;  if(hh<10) cout<<0<<hh<<":";  else cout<<hh<<":";  if(mm<10) cout<<0<<mm<<":";  else cout<<mm<<":";  if(ss<10) cout<<0<<ss<<endl;  else cout<<ss<<endl;
} 

```

编辑于 2019-07-13 22:30:49 回复(0)

Cars on Campus (30)

https://www.nowcoder.com/pat/5/problem/4319

题目大意:给你一n个无序的停车场汽车进出情况日志,包括汽车车牌,记录时间和事件(in 或out),n最大为10000.
然后询问m次,每次给出一个事件点,要求输出该时刻停车场有多少辆车。最后输出在停车场停留最长的车和停留的时间。

分析:
1.一个场景,两个问题,用到的数据较多,比较繁琐。
2.给出的数据无序,可以先处理数据,让时间变得有序再进行下一步。
3.题目中有个大坑,只有同一辆车先后进入的数据有效,只进不出货进了有进这样的
情况一定要特别处理。
4.由于在同一日发生,最多只有86400s,所以每个时刻有多少车辆可以开一个数组来记录,切不可每次都遍历。
...

My code

#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = 10009;
const int maxns = 3600 * 24 + 10;    //the totall second number in a a day
struct Indata{    //the input data
    int time;
    string name;
    bool even;
    bool operator < (const Indata& n){    //the method of sort Indata
        return this->time < n.time;
    }
}indata[maxn];

struct Log{
    int time;    //the seconde from 0:0:0 of a monent
    bool even;    //true mean in and false mean out
};

struct Car{    
    vector<Log>log;    //a Car can have multipult of log
    string name;
    int sumtime;    //total time of stay in campus
}car[maxn];
int car_size = 1;//the length - 1 of car[];

int car_num[maxns];    //the munber of car at any monent

int timeint(){
    int h, m, s;
    scanf("%02d:%02d:%02d", &h, &m, &s);
    return h * 3600 + m * 60 + s;
}
void timestr(int t){
    printf("%02d:%02d:%02d", t / 3600, (t % 3600) / 60, (t % 3600) % 60);
}

int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> indata[i].name;
        indata[i].time = timeint();
        string temp;
        cin >> temp;
        indata[i].even = (temp == "in" ? true : false);
    }
    sort(indata, indata + n);
    map<string, int>nimap;// through name to find index
    Car temp;
    for (int i = 0; i < n; i++){    //devide the indata by carname;
        int index = nimap[indata[i].name];
        if (index == 0){    //the first time to meet it car
            car[car_size].name = indata[i].name;
            car[car_size].sumtime = 0;
            car[car_size].log.push_back({ indata[i].time, indata[i].even });
            nimap[indata[i].name] = car_size++;
        }
        else{
            car[index].log.push_back({ indata[i].time, indata[i].even });
        }
    }

    for (int i = 1; i < car_size; i++){
        for (int j = 0; j < car[i].log.size() - 1; j++) {
            if ( car[i].log[j].even == true && car[i].log[j + 1].even == false ){    //find a pair of avaliable data
                car_num[car[i].log[j].time] += 1;
                car_num[car[i].log[j + 1].time] -= 1;
                car[i].sumtime += car[i].log[j+1].time - car[i].log[j].time;
            }
        }
    }
    int max_time = -1;
    vector<string>ans_car;
    //static the sum_time of each car
    for (int i = 1; i < maxns; i++){
        car_num[i] += car_num[i - 1];
    }
    for (int i = 0; i < m; i++){
        int ask = timeint();
        cout << car_num[ask] << endl;
    }
    // find the longest time
    for (int i = 1; i < car_size; i++){
        max_time = max(max_time, car[i].sumtime);
    }
    //find the car with longest time
    for (int i = 0; i < car_size; i++){
        if (car[i].sumtime == max_time){
            ans_car.push_back(car[i].name);
        }
    }
    sort(ans_car.begin(),ans_car.end());
    for (int i = 0; i < ans_car.size(); i++)cout << ans_car[i] << " ";
    timestr(max_time);
    cout<< endl;
    return 0;
}
发表于 2019-03-26 19:09:22 回复(0)