题解：P11474 [COCI 2024/2025 #3] 公交车 / Autobus

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