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;
}