f439 - 10191 - Longest Nap
題目描述
題目給定一天中多個行程的時間，要求找出最長的連續休息時間，並輸出開始時間和持續時間。時間格式為 hh:mm，行程時間範圍為 10:00 到 18:00。
解題思路
程式碼透過模擬一天的行程來找出最長的休息時間。首先，將輸入的時間轉換為分鐘表示，方便計算時間差。然後，遍歷行程，計算相鄰行程之間的時間間隔，並記錄最長的間隔及其開始時間。最後，將結果轉換回 hh:mm 格式並輸出。
複雜度分析
- 時間複雜度: O(n)，其中 n 是行程的數量。程式碼需要遍歷所有行程一次來計算間隔。
- 空間複雜度: O(n)，程式碼使用兩個大小為 n+1 的陣列
a和b來儲存行程的開始和結束時間。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
int n,x,y,ca;
char g;
int main(){
while(n=read()){
int a[n+1],b[n+1];
for(int i=0;i<n;++i){
x=getchar_unlocked();
x=getchar_unlocked();
y=600+60*(x-48);
g=getchar_unlocked();
x=getchar_unlocked();
y+=(x-48)*10;
x=getchar_unlocked();
y+=x-48;
a[i]=y;
g=getchar_unlocked();
x=getchar_unlocked();
x=getchar_unlocked();
y=600+60*(x-48);
g=getchar_unlocked();
x=getchar_unlocked();
y+=(x-48)*10;
x=getchar_unlocked();
y+=x-48;
b[i]=y;
while(x=getchar_unlocked())
if(x=='\n'||x==-1)break;
}
a[n]=1080;
b[n]=1080;
int ma=0,it,now=600;
for(int i=0;i<=n;++i){
a[i]-=now;
if(a[i]>ma){
ma=a[i];
it=i-1;
}
now=b[i];
}
if(it==-1)
now=600;
else
now=b[it];
printf("Day #%d: the longest nap starts at %d:%d%d and will last for ",++ca,now/60,(now%60)/10,(now%60)%10);
if(ma>=60)
printf("%d hours and %d minutes.\n",ma/60,ma%60);
else
printf("%d minutes.\n",ma%60);
}
}