d251 - 94北縣賽-3-羅馬數字 (Roman)
題目描述
題目要求將以羅馬數字表示的時間，加上時差（7小時30分鐘），並將結果以羅馬數字輸出。輸入包含小時和分鐘，分別以羅馬數字表示。
解題思路
程式首先定義了一個 v 陣列，用於儲存羅馬數字對應的數值。gt 函數將羅馬數字字串轉換為整數，它會檢查相鄰的羅馬數字符號，如果後一個符號的值大於前一個符號，則表示減法，將差值加到結果中。否則，將前一個符號的值加到結果中。pt 函數將整數轉換為羅馬數字字串，它使用貪心策略，從最大的羅馬數字符號開始，盡可能多地減去，直到數值為零。主函數讀取小時和分鐘的羅馬數字字串，使用 gt 函數將它們轉換為整數，然後加上時差（7小時30分鐘，即 450 分鐘），計算出台灣時間的小時和分鐘。最後，使用 pt 函數將台灣時間的小時和分鐘轉換為羅馬數字字串，並輸出。
複雜度分析
- 時間複雜度: O(N)，其中 N 是羅馬數字字串的長度。
gt和pt函數都需要遍歷羅馬數字字串一次。 - 空間複雜度: O(1)，程式使用的額外空間是固定的，不隨輸入大小而變化。
程式碼
#include <iostream>
using namespace std;
int v[301];
int gt(string a){
int al=a.length(),n=0;
for(int i=0;i<al;++i){
if(i<al&&v[a[i+1]]>v[a[i]]){
n+=(v[a[i+1]]-v[a[i]]);
++i;
}
else
n+=v[a[i]];
}
return n;
}
void pt(int a){
if(a>=50){
cout << 'L';
a-=50;
}
if(a>=40){
cout << "XL";
a-=40;
}
while(a>=10){
cout << "X";
a-=10;
}
if(a>=9){
cout << "IX";
a-=9;
}
while(a>=5){
cout << "V";
a-=5;
}
if(a>=4){
cout << "IV";
a-=4;
}
while(a){
cout << "I";
--a;
}
}
int main(){
v['I']=1;
v['V']=5;
v['X']=10;
v['L']=50;
string h,m;
cin >> h >> m;
int hh=gt(h),mm=gt(m);
mm+=hh*60+450;
hh=(mm/60)%24;
mm%=60;
pt(hh);
cout << "\n";
pt(mm);
}