d048 - 11309 - Counting Chaos
題目描述
題目要求找出給定時間之後，下一個迴文時間。時間格式為 HH:MM，其中 HH 的範圍是 0 到 23，MM 的範圍是 0 到 59。迴文時間是指將時間字串反轉後與原字串相同的時間。
解題思路
程式碼首先預先計算所有可能的迴文時間，並將它們儲存在 ans 陣列中。迴文時間的判斷透過 chat 函數實現，該函數檢查一個數字是否為迴文。然後，對於每個輸入的時間，程式碼在 ans 陣列中尋找第一個大於輸入時間的迴文時間，並輸出該時間。如果沒有找到大於輸入時間的迴文時間，則輸出 "00:00"。
複雜度分析
- 時間複雜度: O(n + m)，其中 n 是預先計算迴文時間的數量 (最多 2359)，m 是輸入的測試案例數量。預先計算迴文時間的步驟是 O(n)，對於每個測試案例，在
ans陣列中尋找下一個迴文時間的步驟是 O(n) 的最壞情況，但平均情況下會更快。 - 空間複雜度: O(n)，用於儲存所有迴文時間的
ans陣列。
程式碼
#include <iostream>
using namespace std;
int ans[2000],it,n,a,b;
char g;
inline bool chat(int k){
int tmp=k,tmp2=0;
while(tmp){
tmp2*=10;
tmp2+=tmp%10;
tmp/=10;
}
if(tmp2==k)
return 1;
else
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=0;i<=2359;++i){
if(i%100<60&&chat(i)){
ans[it]=i;
++it;
}
}
cin >> n;
while(n--){
cin >> a >> g >> b;
b+=a*100;
for(int i=0;i<it;++i){
if(b<ans[i]){
cout << ans[i]/1000 << (ans[i]%1000)/100 << ":" << (ans[i]%100)/10 << ans[i]%10 << "\n";
break;
}
if(i==it-1){
cout << "00:00\n";
break;
}
}
}
}