PAT1095 Cars on Campus (30分)

题目大意

    模拟一下停车场的车辆进出的情况。

分析过程

    好久没水过博客了。
    用map存一下车牌号到车辆id的映射，然后再来一个map可以反向映射回去。然后就是建立in/out数组，最后按时间排序，双指针模拟一下车辆的进出配对情况，最后计算的时候利用差分的思想，最后前缀和一下然后可以得到每个时刻的车辆数；cnt数组用于统计每辆车停留的时间。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
int n, m, tot, c[maxn], cnt[maxn], ans[maxn];
map<string, int> mp; //正向映射
map<int, string> rmp; //反向映射
vector<int> in[maxn], out[maxn];
int cha(string x){
	return (x[0] - '0') * 10 + x[1] - '0';
}
int getNum(string str){ //时间转整数
	string h;
	vector<string> v;
	stringstream in(str);
	while(getline(in, h, ':')){
		v.push_back(h);
	}
	return cha(v[0]) * 3600 + cha(v[1]) * 60 + cha(v[2]);
}
string getString(int num){//整数转时间
	string ans;
	int h = num / 3600, m = (num - h * 3600) / 60, s = (num - h * 3600 - m * 60);
	ans.push_back(h/10+'0');
	ans.push_back(h%10+'0');
	ans += ":";
	ans.push_back(m/10+'0');
	ans.push_back(m%10+'0');
	ans += ":";
	ans.push_back(s/10+'0');
	ans.push_back(s%10+'0');
	return ans;
}
void solve(){
	int i, j, k;
	for(i=1;i<=tot;++i){
		sort(in[i].begin(), in[i].end());
		sort(out[i].begin(), out[i].end());
	}
	for(k=1;k<=tot;++k){
		j = 0;
		for(i=0;i<in[k].size();++i){
			while(out[k][j] <= in[k][i]) ++j;	
			if(j < out[k].size()){ //对应时间区间的次数+1 
				while(i+1<in[k].size() && out[k][j] > in[k][i+1]) ++i;
				c[in[k][i]]++;
				c[out[k][j]]--;
				cnt[k] += out[k][j] - in[k][i]; 
			}else break;
			++j;
		}
	}
	ans[0] = c[0];
	for(i=1;i<=100000;++i) ans[i] = ans[i-1] + c[i];
} 
int main(){
	int t, i, j;
	string x, y, z;
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(i=0;i<n;++i){
		cin>>x>>y>>z;
		if(!mp[x]){
			mp[x] = ++tot;
			rmp[tot] = x;
		}
		if(z == "in"){
			in[mp[x]].push_back(getNum(y));
		}else{
			out[mp[x]].push_back(getNum(y));
		}
	}
	solve();
	for(i=0;i<m;++i){
		cin>>x;
		cout<<ans[getNum(x)]<<'\n';
	}
	int maxi = 0;
	for(i=1;i<=tot;++i) maxi = max(maxi, cnt[i]);
	for(i=1;i<=tot;++i){
		if(maxi == cnt[i]){
			cout<<rmp[i]<<' ';
		}
	}
	cout<<getString(maxi)<<'\n';
	return 0;
}