学习经验记录

www.gavinygm.cn

0%

PAT A1095 Cars on Campus

发表于 更新于 分类于
给出N条记录，每条记录给出一辆车的车牌号、当前时刻以及出入校情况(入校(in)还是出校(out))。然后给出K个查询，每个查询给出一个时刻，输出在这个时刻校园内的车辆数。查询完毕后输出在学校停留时间最长的车辆的车牌号(如果有多个，就一并输出)和对应的停留时间。注意：对于同一辆车来说，配对的on和off必须满足在把这辆车的记录按时间顺序排列后，在他们之间不允许出现其他on或者是off的记录；否则将被视为无效记录。

超时解法

第四个测试点运行超时，只得了27分。比较浪费精力的是我是用Time结构体表示时间来计算，其实完全没必要，可以全部转换成秒！！！

解题思路

1、先读取所有记录并保存在结构体数组cars中，然后对其排序，先按照姓名，然后按照时间的先后来排序。

2、然后新建一个结构体数组，保存没对on和out，包括开始时间、结束时间和总时间。得出数组ncars

3、求每辆车一天总的停车时间，由于一辆车可能在一天内不同的时间段，所以要对ncars数组求和再保存另一个数组织中sumcars，此时对sumcars数组排序，最前面的几个就是总时间最多的!

4、最后根据查询判断查询时间是否在开始时间和结束时间之间，在的话就计数加一。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e4+10;
const int K=8*1e4+10;
int n,k;
struct Time{
	int h,m,s;
}qr[K];
struct Car{
	char id[10];
	Time t;
	char status[5];
}cars[N];

struct newCar{
	char id[10];
	Time start,end,total;
}ncars[N/2],sumcars[N/2];

bool cmp(const Car& a,const Car& b){
	if(strcmp(a.id,b.id)!=0) return strcmp(a.id,b.id)<0;
	else if(a.t.h!=b.t.h) return a.t.h<b.t.h;
	else if(a.t.m!=b.t.m) return a.t.m<b.t.m;
	else return a.t.s<b.t.s;
}

bool cmpNcars(const newCar& a,const newCar& b){
	if(a.start.h!=b.start.h) return a.start.h<b.start.h;
	else if(a.start.m!=b.start.m) return a.start.m<b.start.m;
	else a.start.s<b.start.s;
}

bool cmpTotal(const newCar& a,const newCar& b){
	if(a.total.h!=b.total.h) return a.total.h>b.total.h;
	else if(a.total.m!=b.total.m) return a.total.m>b.total.m;
	else if(a.total.s!=b.total.s) return a.total.s>b.total.s;
	else return strcmp(a.id,b.id)<0;
}
bool greater(const Time& a,const Time& b){
	if(a.h!=b.h) return a.h>b.h;
	else if(a.m!=b.m) return a.m>b.m;
	else return a.s>=b.s;
}

//a-b
Time get_gap(const Time& a,const Time& b){
	Time t;
	if(a.s>=b.s) {
		t.s=a.s-b.s;
		if(a.m>=b.m){
			t.m=a.m-b.m;
			t.h=a.h-b.h;
		}else{
			t.m=a.m+60-b.m;
			t.h=a.h-b.h-1;
		}
	}
	else{
		t.s=a.s+60-b.s;
		if(a.m-1>=b.m){
			t.m=a.m-1-b.m;
			t.h=a.h-b.h;
		}else{
			t.m=a.m-1+60-b.m;
			t.h=a.h-b.h-1;
		}
	}
	return t;
}
Time get_sum(const Time& a,const Time& b){
	Time t;
	if(a.s+b.s>=60){
		t.s=a.s+b.s-60;
		if(a.m+b.m+1>=60){
			t.m=a.m+b.m+1-60;
			t.h=a.h+b.h+1;	
		}else{
			t.m=a.m+b.m+1;
			t.h=a.h+b.h;
		}
	}else{
		t.s=a.s+b.s;
		if(a.m+b.m>=60){
			t.m=a.m+b.m-60;
			t.h=a.h+b.h+1;	
		}else{
			t.m=a.m+b.m;
			t.h=a.h+b.h;
		}
	}
	return t;
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%s %d:%d:%d %s",&cars[i].id,&cars[i].t.h,&cars[i].t.m,&cars[i].t.s,&cars[i].status);	
	}
	for(int i=0;i<k;i++){
		scanf("%d:%d:%d",&qr[i].h,&qr[i].m,&qr[i].s);
	}
	
	sort(cars,cars+n,cmp);

//	for(int i=0;i<n;i++){
//		printf("%s %02d:%02d:%02d %s\n",cars[i].id,cars[i].t.h,cars[i].t.m,cars[i].t.s,cars[i].status);	
//	}
	//找出每一对in和out，保存到新的结构体数组ncars中，
	//每个结构体包括开始时间、结束时间和该停车时间段时长 
	int c=0;
	for(int i=0;i<n-1;i++){
		if(strcmp(cars[i].id,cars[i+1].id)==0&&
			strcmp(cars[i].status,"in")==0&&
			strcmp(cars[i+1].status,"out")==0	
		){
			strcpy(ncars[c].id,cars[i].id);
			ncars[c].start=cars[i].t;
			ncars[c].end=cars[i+1].t;
			ncars[c].total=get_gap(cars[i+1].t,cars[i].t);
			c++;
			i++;	
		}
	}	
	
	//将车牌相同的总停车时间求和 
	int p=0;
	//设置中间变量
	char ids[10];
	strcpy(ids,ncars[0].id);
	Time tmp=ncars[0].total;
	for(int i=1;i<c;i++){
		if(strcmp(ncars[i].id,ids)!=0){
			strcpy(sumcars[p].id,ids);
			sumcars[p].total=tmp;
			strcpy(ids,ncars[i].id);//更新中间变量 
			tmp=ncars[i].total;
			p++; 
		}else{
			tmp=get_sum(tmp,ncars[i].total);
		}
	}
	//把最后一个值加入sumcars 
	sumcars[p].total=tmp;
	strcpy(sumcars[p].id,ids);
	p++;
	sort(sumcars,sumcars+p,cmpTotal);//排序，找出最长停车时间的车牌 
	//------------------------------>到此处sumcars中存放最长停车时间 
	
	sort(ncars,ncars+c,cmpNcars);//先把ncars按照start时间排序 
	//下面开始根据ncars来判断每个query查询时间停车数 
	for(int i=0;i<k;i++){
		int cnt=0;
		for(int j=0;j<c;j++){//可能超时！！！ 
			if(greater(qr[i],ncars[j].start)&&!greater(qr[i],ncars[j].end)){
				cnt++;
			} 
		}
		printf("%d\n",cnt);
	}
	
	newCar ans=sumcars[0];
	for(int i=0;i<p;i++){
		if(sumcars[i].total.h==ans.total.h&&
			sumcars[i].total.m==ans.total.m&&
			sumcars[i].total.s==ans.total.s
		){
			printf("%s ",sumcars[i].id);
		}
	}
	printf("%02d:%02d:%02d",ans.total.h,ans.total.m,ans.total.s);
	
	//printf("%s %02d:%02d:%02d %02d:%02d:%02d-->%02d:%02d:%02d\n",
//		sumcars[i].id,sumcars[i].start.h,sumcars[i].start.m,sumcars[i].start.s,
//		sumcars[i].end.h,sumcars[i].end.m,sumcars[i].end.s,
//		sumcars[i].total.h,sumcars[i].total.m,sumcars[i].total.s);
	
	return 0;
}

AC解法

解题思路

查找时使用二分法先找出所有小于当前查询的query的位置，然后往前找出所有车辆的end时间大于当前查询的汽车数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e4 + 10;
const int K = 8e4 + 10;
struct Car {
    char plate[8];
    int curTime;
    int endTime;
    int parkTime;
    char status[5];
} cars[N],ans[N],res[N];
int n, m, query[K];
int k=0;
int changeTime(int h, int m, int s) {
    return (h * 60 + m) * 60 + s;
}

void TimeTo24(int cur, int &h, int &m, int &s) {
    s = cur % 60;
    cur /= 60;
    m = cur % 60;
    h = cur / 60;
}

bool cmpCur(const Car &a, const Car &b) {
    if (strcmp(a.plate, b.plate) != 0) return strcmp(a.plate, b.plate) < 0;
    else return a.curTime < b.curTime;
}
bool cmpPark(const Car &a, const Car &b){
    if (a.parkTime!=b.parkTime) return a.parkTime>b.parkTime;
    else return strcmp(a.plate,b.plate)<0;
}
bool cmpAns(const Car &a, const Car &b){
    return a.curTime<b.curTime;
}
int binarySearch(int x){
    int l=0,r=k,mid;
    while(l<r){
        mid=(l+r)/2;
        if(ans[mid].curTime>x){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    return l;
}

int main() {
    scanf("%d%d", &n, &m);
    int hh, mm, ss;
    for (int i = 0; i < n; i++) {
        scanf("%s %d:%d:%d %s", &cars[i].plate, &hh, &mm, &ss, &cars[i].status);
        cars[i].curTime = changeTime(hh, mm, ss);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d:%d:%d", &hh, &mm, &ss);
        query[i] = changeTime(hh, mm, ss);
    }
    sort(cars, cars + n, cmpCur);

    for (int i = 0; i < n ; i++) {
        if (strcmp(cars[i].plate, cars[i + 1].plate) == 0 &&
            strcmp(cars[i].status, "in") == 0 &&
            strcmp(cars[i + 1].status, "out")==0) {
            ans[k]=cars[i];
            ans[k].endTime=cars[i+1].curTime;
            ans[k].parkTime=cars[i+1].curTime-cars[i].curTime;
            i++;
            k++;
        }
    }
    sort(ans,ans+k,cmpAns);
//    for(int i=0;i<k;i++){
//        printf("%s cur:%d end:%d park:%d\n",ans[i].plate,ans[i].curTime,ans[i].endTime,ans[i].parkTime);
//    }
    //找出这个时间点的停车数
    for(int i=0;i<m;i++){
        int ct=0;
        int p=binarySearch(query[i]);
//        printf("%s cur:%d query:%d p:%d\n",ans[p].plate,ans[p].curTime,query[i],p);
        for(int j=p-1;j>=0;j--){
            if(ans[j].endTime>query[i]){
                ct++;
            }
        }
        printf("%d\n",ct);
    }

    //下面是合并每一辆车的总停车时间
    sort(ans, ans + k, cmpCur);
    char id[8]="xxx";
    int t=0;
    for(int i=0;i<k;i++){
        if(strcmp(ans[i].plate,id)!=0){
            res[t++]=ans[i];
            strcpy(id,ans[i].plate);
        }else{
            res[t-1].parkTime+=ans[i].parkTime;
        }
    }
    sort(res,res+t,cmpPark);
    if(res[0].parkTime!=0) printf("%s",res[0].plate);
    for(int i=1;i<t;i++){
        if(res[i].parkTime==res[0].parkTime){
            printf(" %s",res[i].plate);
        }else break;
    }
    TimeTo24(res[0].parkTime,hh,mm,ss);
    printf(" %02d:%02d:%02d",hh,mm,ss);
    return 0;
}

算法笔记解法

解题思路

待补

本文标题:PAT A1095 Cars on Campus

文章作者:GavinYGM

发布时间:2020年08月26日 - 17:08

最后更新:2020年09月09日 - 16:09

原始链接:http://www.gavinygm.cn/2020/08/26/PAT-A1095-Cars-on-Campus/

许可协议: 转载请保留原文链接及作者。