[数据结构与算法]PAT (Advanced Level) 1095——输入信息处理+类莫队算法

题目传送门

很复杂的题意和输入信息说明：

• 按时间排序后，每一个in记录与同车牌号的最近的out记录匹配
  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.

但是题目给出的输入并不是按照时间排序的
所以，我们需要将读入的信息先原封不动的储存起来
之后按照时间排序，花费$O(n^2)$的时间找到匹配的进出记录，并重新存储
重新存储的数据还是需要按照时间排序
在线处理查询，利用类似莫队的方法扫描计算停车数
如果在查询时间之前的记录，in记录停车数增加，out记录停车数减少

需要注意的是，统计停车时间最长的车辆时，需要将同一辆车的停车时长全部累加
也就是说，同一辆车可能在一天的时间内多次进出校园

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;

const int N = 10005;
int n, m;
map<string, int> myMap;
struct node {
	char plate_number[15];
	int time;
	char state[10];
};
node car[N];
node good_car[N / 2];
int tot = 0;

int cmp(const node& A, const node& B) {
	return (A.time < B.time);
}

int pmc(const node& A, const node& B) {
	return strcmp(A.plate_number, B.plate_number) <= 0;
}

int get_time(char* time) {
	int h = ((time[0] - '0') * 10 + time[1] - '0') * 60 * 60;
	int m = ((time[3] - '0') * 10 + time[4] - '0') * 60;
	int s = ((time[6] - '0') * 10 + time[7] - '0');
	return h + m + s;
}

void prt(int t) {
	int h = t / 3600;
	int m = (t % 3600) / 60;
	int s = t % 60;
	printf("%02d:%02d:%02d", h, m, s);
}

int ans_max_time = 0;
node ans_car_number[N / 2];
int ans_tot = 0;

int main()
{
	scanf("%d %d",&n,&m);
	char number[15];
	char time[15];
	char state[10];
	for (int i = 1; i <= n; ++i) {
		scanf("%s %s %s",&number,&time,&state);
		strcpy(car[i].plate_number, number);
		strcpy(car[i].state, state);
		car[i].time = get_time(time);
	}

	sort(car + 1, car + 1 + n, cmp);
	
	for (int i = 1; i <= n; ++i) {
		if (car[i].state[0] == 'i') 
			for (int j = i + 1; j <= n; ++j) {
				if (strcmp(car[i].plate_number, car[j].plate_number) == 0) {   //第一个车牌号相同的记录
					if (car[j].state[0] == 'o') {
						good_car[++tot] = car[i];
						good_car[++tot] = car[j];
						car[j].state[0] = '\0';   //删除已匹配的记录
						int t = car[j].time - car[i].time;
						char number[15];
						strcpy(number, car[i].plate_number);
						myMap[number] += t;   //累计停车时间
						if (myMap[number] > ans_max_time) {
							ans_max_time = myMap[number];
							ans_tot = 1;
							strcpy(ans_car_number[1].plate_number, number);
						}
						else if (myMap[number] == ans_max_time) {
							ans_tot++;
							strcpy(ans_car_number[ans_tot].plate_number, number);
						}
					}
					break;
				}
			}
	}

	sort(good_car + 1, good_car + 1 + tot, cmp);
	int index = 1;
	int cnt = 0;
	for (int i = 1; i <= m; ++i) {
		scanf("%s", &time);
		int t = get_time(time);
		while (good_car[index].time <= t && index <= tot) {
			if (good_car[index].state[0] == 'i')
				++cnt;
			else --cnt;
			++index;
		}
		printf("%d\n", cnt);
	}

	sort(ans_car_number + 1, ans_car_number + 1 + ans_tot, pmc);
	for (int i = 1; i <= ans_tot; ++i) printf("%s ", ans_car_number[i].plate_number);
	prt(ans_max_time);
	return 0;
}

超强干货来袭

云风专访：近40年码龄，通宵达旦的技术人生