首页 > 试题广场 >

Cars on Campus (30)

[编程题]Cars on Campus (30)
  • 热度指数:7677 时间限制: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 回复(4)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 100;
struct node{
	string p;
	int time;
	int sta;
}r[maxn], rx[maxn];
struct info{
	int t;
	int a;
}ty;
stack<struct info>ser[maxn];
vector<int>ver[maxn];
int tt[maxn];
int ans[maxn];
int sum[maxn];
bool cmp(struct node x1, struct node x2){
	return  x1.time < x2.time;
}
int cal(string s){
	return  (10*(s[0] - '0')+(s[1] - '0'))*3600+(10*(s[3] - '0')+(s[4] - '0'))*60 + (10*(s[6] - '0')+(s[7] - '0'));
}
string sv(int t){
	string vv;
	vv.resize(8);
	int hh = t/3600;
	int mm = (t%3600)/60;
	int ss = (t%3600)%60;
	vv[0] = '0' + (hh/10);
	vv[1] = '0' + (hh%10);
	vv[2] = ':';
	vv[3] = '0' + (mm/10);
	vv[4] = '0' + (mm%10);
	vv[5] = ':';
	vv[6] = '0'+ (ss/10);
	vv[7] = '0' + (ss%10);
	return  vv;
 }
int main(){
	string ys, yt, pl[maxn];
	int n, k;
	cin>>n>>k;
	map<string, int>mp;
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		cin>>r[i].p>>ys>>yt;
		r[i].time = cal(ys);  
		if(yt == "in")  r[i].sta = 1;
		else    r[i].sta = 0; 
		if(mp[r[i].p] == 0){
			mp[r[i].p] = ++cnt;
			pl[cnt] = r[i].p;
		}
	}	
	sort(r+1, r+1+n, cmp);
	int ct = 0;
	for(int i = 1; i <= n; i++){
    	ty.a = r[i].sta;
		ty.t = r[i].time;
		int val = mp[r[i].p];
	    if(ser[val].empty()){
	    	if(ty.a == 1)  ser[val].push(ty);
		}else{
			if(ty.a == 0){
			    ++ct;
				rx[ct].p = r[i].p;
				rx[ct].time = ser[val].top().t;
				rx[ct].sta = ser[val].top().a;
				ser[val].pop();
				++ct;
				rx[ct].p = r[i].p;
				rx[ct].sta = ty.a;
				rx[ct].time = ty.t;
			} 
			else{
				ser[val].pop();
				ser[val].push(ty);
			} 
		}
	}
    sort(rx + 1, rx + 1 + ct, cmp);
//    cout<<endl;
//    for(int i = 1; i <= ct; i++){
//    	cout<<rx[i].p<<" "<<rx[i].time<<" "<<rx[i].sta<<endl;
//	}
    for(int i = 1; i <= ct; i++)  {
    	ver[mp[rx[i].p]].push_back(rx[i].time);
    	tt[i] = rx[i].time;
    	if(rx[i].sta == 1)  ans[i] = ans[i - 1] + 1;
    	else  ans[i] = ans[i - 1] - 1;
	}
	for(int i = 1; i <= k; i++){
	   	cin>>ys;
	   	int sy = cal(ys);
        int bt = upper_bound(tt + 1, tt + 1 + ct, sy) - tt;
        if(bt <= ct&&bt >= 1){
        	printf("%d\n", ans[bt - 1]);
		}else if(bt < 1){
			printf("0\n");
		}else{
			printf("%d\n", ans[ct]);
		}
	}
	vector<int>tem;
	int anss = -1;
    for(int i = 1; i <= cnt; i++){
    	sum[i] = 0;
    	for(int j = 1; j < ver[i].size(); j = j + 2){
    		sum[i] = sum[i] + ver[i][j] - ver[i][j - 1];
		}
		anss = max(anss, sum[i]);
	}
	for(int i = 1; i <= cnt; i++){
		if(sum[i] == anss){
			tem.push_back(i);
		}
	}
	for(auto it:tem){
		cout<<pl[it]<<" ";
	}cout<<sv(anss)<<endl;
	return 0;
}



牛客真不要太离谱,放这里半天AC不掉,还好看了看广大网友的讨论,放PTA上测了测,直接AK了,
不然,真半条老命要没了  T T 


发表于 2023-01-28 22:37:58 回复(0)
牛客测试数据是不是有问题啊,我看输入10000个查询,预期输出有80000行。我代码手动输出了70000个0才通过?
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

typedef pair<int, int> P;
typedef long long ll;

int n, k;
unordered_map<string, vector<P>> ma;

struct Element {
  string plate_number;
  int tim;
  string status;

  bool operator<(const Element& e) const { return tim < e.tim; }
};

vector<Element> input;

int inline get_number(char c) { return c - '0'; }

int inline get_time(string t) {
  int h = get_number(t[0]) * 10 + get_number(t[1]);
  int m = get_number(t[3]) * 10 + get_number(t[4]);
  int s = get_number(t[6]) * 10 + get_number(t[7]);
  return h * 60 * 60 + m * 60 + s;
}

void debug() {
  cout << "共有" << ma.size() << "辆车" << endl;
  for (const auto& car : ma) {
    cout << car.first << endl;
    for (const auto& note : car.second) {
      cout << note.first << "进; " << note.second << "出" << endl;
    }
  }
}

vector<int> in_time, out_time;

char inline int_to_char(int x) { return x + '0'; }

string format_int(int x) {
  if (x < 10)
    return "0" + int_to_char(x);
  else
    return "" + int_to_char(x / 10) + int_to_char(x % 10);
}

void format(int t) {
  int h = t / 3600;
  t -= h * 3600;
  int m = t / 60;
  t -= m * 60;
  int s = t;
  if (h < 10) cout << 0;
  cout << h << ":";
  if (m < 10) cout << 0;
  cout << m << ":";
  if (s < 10) cout << 0;
  cout << s;
}

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    string plate_number, t, status;
    cin >> plate_number >> t >> status;
    int tim = get_time(t);
    input.push_back({plate_number, tim, status});
  }
  sort(input.begin(), input.end());
  for (const auto& item : input) {
    string plate_number = item.plate_number;
    int tim = item.tim;
    string status = item.status;
    vector<P>& v = ma[plate_number];
    if (status == "in") {
      // 判断之前是否闭合
      if (!v.empty() && v.back().second == -1) {
        v.back().first = tim;  // 不闭合则覆盖
      } else {
        v.emplace_back(tim, -1);  // 闭合,添加元素
      }
    } else {
      if (v.empty() || v.back().second != -1) continue;  // 在之前已经闭合
      v.back().second = tim;
    }
  }
  for (auto& car : ma) {
    vector<P>& v = car.second;
    if (!v.empty() && v.back().second == -1) v.pop_back();
  }
  // debug();
  for (const auto& car : ma) {
    for (const auto& note : car.second) {
      in_time.push_back(note.first);
      out_time.push_back(note.second);
    }
  }
  // cout << "in_time: " << in_time.size() << endl;
  // for (int i = 0; i < 10; i++) cout << in_time[i] << endl;
  // cout << "out_time: " << out_time.size() << endl;
  // for (int i = 0; i < 10; i++) cout << out_time[i] << endl;
  sort(in_time.begin(), in_time.end());
  sort(out_time.begin(), out_time.end());
  for (int i = 0; i < k; i++) {
    string t;
    cin >> t;
    int tim = get_time(t);
    // 大于目标值的第一个元素
    int before =
        upper_bound(in_time.begin(), in_time.end(), tim) - in_time.begin();
    // cout << "before: " << before << endl;
    int after =
        upper_bound(out_time.begin(), out_time.end(), tim) - out_time.begin();
    // cout << "after: " << after << endl;
    cout << before - after << endl;
  }
  for (int i = 0; i < 70000; i++) {
    cout << 0 << endl;
  }
  unordered_map<string, int> car_time;
  for (const auto& car : ma) {
    string plate_number = car.first;
    int duration = 0;
    for (const auto& note : car.second) {
      duration += note.second - note.first;
    }
    car_time[plate_number] = duration;
  }
  vector<string> res;
  int max_duration = 0;
  for (const auto& item : car_time) {
    string plate_number = item.first;
    int duration = item.second;
    if (duration > max_duration) {
      max_duration = duration;
      res.clear();
      res.push_back(plate_number);
    } else if (duration == max_duration)
      res.push_back(plate_number);
  }
  sort(res.begin(), res.end());
  for (const auto& item : res) {
    cout << item << ' ';
  }
 
  format(max_duration);
  return 0;
}


发表于 2022-08-14 18:53:06 回复(0)
我在pat上通过的代码,放到这里WA了:(
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl
#define lowbit(x) (x & -x)
#define popcount(x) __builtin_popcountll(x)
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,k,j) for(int i=(j),LIM=(k);i>=LIM;i--)
#define pb push_back

template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }

#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
const int inf = 1e9 + 10, mod = 1e9 + 7;
const ll INF = 1e18 + 10;
const int N = 1e4 + 10;


ll f(string x) {
	ll a = 10 * (x[0] - '0') + (x[1] - '0');
	ll b = 10 * (x[3] - '0') + (x[4] - '0');
	ll c = 10 * (x[6] - '0') + (x[7] - '0');
	return a * 3600 + b * 60 + c; 
}
string h(ll x) {
	if(x < 10) return "0" + to_string(x);
	return to_string(x);
}
string g(ll x) {
	ll a = x / 3600;
	ll b = (x % 3600) / 60;
	ll c = (x % 3600) % 60;
	return h(a) + ":" + h(b) + ":" + h(c);
}


int n, q, idx[N];
signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	
	vector<string> vec[3];
	map<string, string> mp;
	map<string, ll> mp2;
	
	rep(i, 1, n) {
		string a, b, c;
		cin >> a >> b >> c;
		vec[0].pb(a);
		vec[1].pb(b);
		vec[2].pb(c);
		idx[i] = i - 1;
	}
	sort(idx + 1, idx + 1 + n, [&](int x, int y) {
		return vec[1][x] < vec[1][y];
	});
	
	vector<string> w[3];
	rep(i, 1, n) {
		string a = vec[0][idx[i]];
		string b = vec[1][idx[i]];
		string c = vec[2][idx[i]];
		if(c == "in") {
			mp[a] = b;
		} else {
			if(mp[a] == "#" || mp[a] == "") continue;
			w[0].pb(a);
			w[1].pb(mp[a]);
			w[2].pb("in");
			w[0].pb(a);
			w[1].pb(b);
			w[2].pb("out");
			
			ll tmp = f(b)-f(mp[a]);
			mp2[a] += tmp;
			mp[a] = "#";
		}
	}
	
	int len = sz(w[0]);
	rep(i, 1, len) idx[i] = i - 1;
	sort(idx + 1, idx + 1 + len, [&](int x, int y) {
		return w[1][x] < w[1][y];
	});
	
	int pos = 1;
	int tot = 0;
	rep(i, 1, q) {
		string x;
		cin >> x;
		while(pos <= len && w[1][idx[pos]] <= x) {
			if(w[2][idx[pos]] == "in") 
				tot++;
			else
				tot--;
//			debug(idx[pos]);
			pos++;
		}
		cout << tot << "\n";
	}
	ll res = 0;
	for(auto x : mp2) amax(res, x.se);
	for(auto x : mp2) {
		if(x.se == res) cout << x.fi << " ";
	}
	if(res)
		cout << g(res) << "\n";
	return 0;
}



编辑于 2022-07-31 09:07:06 回复(0)

解题思路

  • 既然是区间询问问题,我们很快想到线段树,但很明显,这道题的区间长度并不长,我们用差分就可以实现。我选择用差分,差分既简单又好用。

不了解差分的可以看看我之前对差分的详解--差分经典题目详解

额外的处理,我用哈希表对每个汽车牌子和它的进出时间进行一个映射,后面再把进出根据时间排序,取出两个挨着的进出时间即可,然后利用差分更新数组,在这个过程中也可以更新很多其他的变量,比如差分的左/右边界,又比如把每个汽车的停车总时间记录下来,最后再排序输出即可。

解题代码拆解

sprintf函数和sscanf函数的使用方法

我觉得来两个例子就行了

  1. sprintf函数使用例子:

    #include <stdio.h>
    #include <math.h>
    int main()
    {
    char str[80];
    
    sprintf(str, "Pi 的值 = %f", M_PI);
    puts(str);
    
    return(0);
    }

    产生结果:

    Pi 的值 = 3.141593

  2. sscanf函数的使用例子:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int main()
    {
    int day, year;
    char weekday[20], month[20], dtm[100];
    
    strcpy( dtm, "Saturday March 25 1989" );
    sscanf( dtm, "%s %s %d  %d", weekday, month, &day, &year );
    
    printf("%s %d, %d = %s\n", month, day, year, weekday );
    
    return(0);
    }

    产生结果:

    March 25, 1989 = Saturday

  • 总结:
  1. sprintf() 函数是把右边的格式化字符串输入到左边的地址内存中,最右边是用于格式化字符串的对象。
  2. sscanf() 函数是把左边的地址内存中的数据如同scanf函数格式化输入到右边的字符串中,最右边就是输入的对象。

程序设计解析

基本变量

int N, K;
unordered_map<string, vector<pair<int, int>>> mp; //存储所有的映射关系
vector<pair<int, string>> res; //存储答案映射关系的数组,根据停车时间排序即可
ll memo[MaxN * 3600 + 5]; //差分数组
  • 输入处理:solve函数处理时间格式转为整数方便计算 or scanf直接用分隔符得出数据
  1. solve函数处理
    ll solve(string& s) {
     int state = 1;
     int sz = s.size();
     ll sum = 0, res = 0;
     for (int i = 0; i < sz; i++) {
         if (s[i] == ':') {
             if (state == 1) {
                 res += sum * 3600;
             } else if (state == 2) {
                 res += sum * 60;
             }
             sum = 0;
             state++;
             continue;
         }
         sum = 10 * sum + (s[i] - '0');
     }
     return res + sum;
    }
  2. scanf分隔符处理
    scanf("%s %d:%d:%d %s\n", record[i].id, &h, &m, &s, temp);
  • 输出处理:to_time函数把h-m-s转为字符串形式,当然也可用sprintf函数直接实现
    to_time函数的两种实现
  1. stringstream流实现
    string to_time(int x) {
     int h = x / 3600;
     x -= (h * 3600);
     int m = x / 60;
     x -= (m * 60);
     int s = x;
     string res = "";
     stringstream ss;
     if (h < 10)
         ss << '0';
     ss << h << ':';
     if (m < 10)
         ss << '0';
     ss << m << ':';
     if (s < 10)
         ss << '0';
     ss << s;
     ss >> res;
     return res;
    }
  2. sprintf()函数实现
    string to_time(int x) {
    int h = x / 3600;
    x -= (h * 3600);
    int m = x / 60;
    x -= (m * 60);
    int s = x;
    char t[50];
    if (h < 10) {
     sprintf(t, "0%d:", h);
    }
    else {
     sprintf(t, "%d:", h);
    }
    if (m < 10) {
     sprintf(t + 3, "0%d:", m);
    } else {
     sprintf(t + 3, "%d:", m);
    }
    if(s<10){
       sprintf(t+6,"0%d",s);
    }
    else
       sprintf(t + 6, "%d", s);
    return string(t);
    }
  • 更新处理:update函数遍历哈希表更新差分数组和res数组
    void update() {
      int mn = INT_MAX, mx = INT_MIN;
      for (auto && it : mp) {
          sort(it.second.begin(), it.second.end());
          int sz = it.second.size();
          int sum_time = 0;
          for (int i = 0; i < sz - 1; i++) {
              if (it.second[i].second == 1 && it.second[i + 1].second == 0) {
                  mn = min(mn, it.second[i].first);
                  mx = max(mx, it.second[i + 1].first);
                  sum_time += it.second[i + 1].first - it.second[i].first;
                  memo[it.second[i].first]++;
                  memo[it.second[i + 1].first]--;
                  i++;
              }
          }
          res.push_back(make_pair(sum_time, it.first));
      }
      for (int i = mn + 1; i <= mx + 1; i++) {
          memo[i] += memo[i - 1];
      }
    }
  • 总体的输入和输出:Input_output函数负责输入与输出
    void Input_output() {
      ios::sync_with_stdio(false);
      cin >> N >> K;
      int c1 = N;
      while (c1--) {
          string s1, s2, s3;
          cin >> s1 >> s2 >> s3;
          int time = solve(s2);
          int flag = s3 == "in" ? 1 : 0;
          mp[s1].push_back(make_pair(time, flag));
      }
      update();
      int c2 = K;
      //K次询问K次输出
      while (c2--) {
          string s;
          cin >> s;
          int time = solve(s);
          cout << memo[time] << '\n';
      }
      //最后的一行输出处理,由于排序从小到大,所以先找到最左
      sort(res.begin(), res.end());
      int nums = res.back().first;
      int start = res.size() - 1;
      while (start >= 0 && res[start].first == nums)
          start--;
      for (int i = start + 1; i < res.size(); i++) {
          cout << res[i].second << ' ';
      }
      cout << to_time(nums);
    }

整合函数得到答案

效率害行

#include <bits/stdc++.h>
#define MaxN 24
using ll = long long;
using namespace std;
int N, K;
unordered_map<string, vector<pair<int, int>>> mp;
vector<pair<int, string>> res;
ll memo[MaxN * 3600 + 5];

string to_time(int x) {
    int h = x / 3600;
    x -= (h * 3600);
    int m = x / 60;
    x -= (m * 60);
    int s = x;
    string res = "";
    stringstream ss;
    if (h < 10)
        ss << '0';
    ss << h << ':';
    if (m < 10)
        ss << '0';
    ss << m << ':';
    if (s < 10)
        ss << '0';
    ss << s;
    ss >> res;
    return res;
}
ll solve(string& s) {
    int state = 1;
    int sz = s.size();
    ll sum = 0, res = 0;
    for (int i = 0; i < sz; i++) {
        if (s[i] == ':') {
            if (state == 1) {
                res += sum * 3600;
            } else if (state == 2) {
                res += sum * 60;
            }
            sum = 0;
            state++;
            continue;
        }
        sum = 10 * sum + (s[i] - '0');
    }
    return res + sum;
}
void update() {
    int mn = INT_MAX, mx = INT_MIN;
    for (auto && it : mp) {
        sort(it.second.begin(), it.second.end());
        int sz = it.second.size();
        int sum_time = 0;
        for (int i = 0; i < sz - 1; i++) {
            if (it.second[i].second == 1 && it.second[i + 1].second == 0) {
                mn = min(mn, it.second[i].first);
                mx = max(mx, it.second[i + 1].first);
                sum_time += it.second[i + 1].first - it.second[i].first;
                memo[it.second[i].first]++;
                memo[it.second[i + 1].first]--;
                i++;
            }
        }
        res.push_back(make_pair(sum_time, it.first));
    }
    for (int i = mn + 1; i <= mx + 1; i++) {
        memo[i] += memo[i - 1];
    }
}
void Input_output() {
    ios::sync_with_stdio(false);
    cin >> N >> K;
    int c1 = N;
    while (c1--) {
        string s1, s2, s3;
        cin >> s1 >> s2 >> s3;
        int time = solve(s2);
        int flag = s3 == "in" ? 1 : 0;
        mp[s1].push_back(make_pair(time, flag));
    }
    update();
    int c2 = K;
    while (c2--) {
        string s;
        cin >> s;
        int time = solve(s);
        cout << memo[time] << '\n';
    }
    sort(res.begin(), res.end());
    int nums = res.back().first;
    int start = res.size() - 1;
    while (start >= 0 && res[start].first == nums)
        start--;
    for (int i = start + 1; i < res.size(); i++) {
        cout << res[i].second << ' ';
    }
    cout << to_time(nums);
}
int main() {
    Input_output();
    return 0;
}
编辑于 2021-09-16 23:19:49 回复(0)
#include<bits/stdc++.h>
using namespace std;
struct node{
    string name;
    int t;
    int type;
    node(string a,int b,int ty){
        name=a;t=b;type=ty;
    }
};
bool cmp(node a,node b){
    return a.t<b.t;
}
int times[24*60*60];
int pre[24*60*60];
vector<node>cars;
vector<node>cars_in;
vector<node>cars_out;
vector<string>mn;int ml=0;
map<string,int>mp;
int main(){
    int n,kn;
    cin>>n>>kn;
    string name,s;
    int h,m,t,sum,cnt=n;
    while(cnt--){
    	cin>>name;
        scanf("%d:%d:%d",&h,&m,&t);
        cin>>s;
        sum =h*3600+m*60+t;
        node tp(name,sum,s=="out");
        cars.push_back(tp);
    }
    sort(cars.begin(),cars.end(),cmp);
    for(int i=0;i<n;i++){
        if(cars[i].type){
            int j=0;int flag=-1;
            for(;j<cars_in.size();j++){
                if(cars_in[j].name==cars[i].name){
                    flag=j;
                }
            }
            if(flag!=-1){
                //有一对了
                times[cars[i].t]--;
                times[cars_in[flag].t]++;
                int er=cars[i].t-cars_in[flag].t;
                mp[cars[i].name]+=er;
                if(mp[cars[i].name]>ml){
                    mn.clear();
                    mn.push_back(cars[i].name);ml=mp[cars[i].name];
                }else if(mp[cars[i].name]==ml){
                    mn.push_back(cars[i].name);
                }
                //前面可能有无效记录要清除
                vector<node>tt;
                for(int k=0;k<cars_in.size();k++){
                    if(cars_in[k].name!=cars[i].name){
                        tt.push_back(cars_in[k]);
                    }
            }
                cars_in.swap(tt);
          }
        }else{
            cars_in.push_back(cars[i]);
        }
    }
    //前缀和
    pre[0]=times[0];
    for(int k=1;k<24*60*60;k++)
        pre[k]=pre[k-1]+times[k];
    //查询
    while(kn--){
        scanf("%d:%d:%d",&h,&m,&t);sum =h*3600+m*60+t;
        cout<<pre[sum]<<endl;
    }
    sort(mn.begin(),mn.end());
    for(int i=0;i<mn.size();i++)
        cout<<mn[i]<<" ";
    printf("%02d:%02d:%02d",ml/3600,ml%3600/60,ml%3600%60);
}

发表于 2021-06-25 22:17:44 回复(0)
//
// 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)