自动搬运

查看原文

来自洛谷，原作者为

	yi_hr mamihlapinatapai

搬运于2025-08-24 23:07:41，当前版本为作者最后更新于2024-12-30 16:39:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

模拟

本题注重细节！！！

思路： $O(N^2)$ 暴力，其中 $N$ 为值域 $1440$。输入后将两条路径的 $t_{\texttt{发车时间}}\rightarrow t_{\texttt{到达时间}}$ 分别用两个数组记录下来，然后暴力枚举两条路径的组合，维护 $ans$ 最小值，输出即可。
细节：

1. 一条路线可能横跨两天，需将结束时间 $+1440$ 分钟存储。
2. 我们选出两条路线后，若第二条路线的开始时间小于第一条路线的结束时间，第二天路线需要在下一天乘坐，即 $+1440$ 分钟。

代码实现

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
inline int read(){
	register int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0'){c=getchar();}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x;
}
const int N=1449;
int n,m1,m2,ans=INF;
string s;
int h1,t1,h2,t2;
bool f1,f2;
int a1[N],a2[N];
inline int num(int h,int m){//计算时刻，转换为分钟 
	return h*60+m;
}
inline int solve(int i,int j){
	if(a1[i]==INF||a2[j]==INF) return INF;
	return a2[j]+(a1[i]-j+1440)/1440*1440-i+1;
}
int cnt1,cnt2;
int main(){
	memset(a1,INF,sizeof(a1));
	memset(a2,INF,sizeof(a2));
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		h1=read();t1=read();h2=read();t2=read();
		//使用快读来应对题目中的输入方式 
		if(s[0]=='Z'){
			f1=1;
			cnt1=num(h1,t1);cnt2=num(h2,t2);
			if(cnt2<cnt1) cnt2+=1440;//结束时间在下一天 
			a1[cnt1]=cnt2;
		}else{
			f2=1;
			cnt1=num(h1,t1);cnt2=num(h2,t2);
			if(cnt2<cnt1) cnt2+=1440;
			a2[cnt1]=cnt2;
		}
	}
	if(!f1||!f2){
		cout<<"NEMOGUCE";
		return 0;
	}
	for(int i=0;i<=1440;i++){
		if(a1[i]==INF)continue;
		for(int j=0;j<=1440;j++){
			if(a2[j]==INF)continue;
			ans=min(ans,solve(i,j));
		}
	}
	printf("%d:",ans/60);
	if(ans%60<10)cout<<0;
	printf("%d",ans%60);
	return 0;
}