h385 - 12970: Alcoholic Pilots
題目描述
題目給定兩個飛機的速度和距離，要求判斷哪個飛機先到達機場，並計算兩個飛機到達機場的平均時間，以簡化分數的形式輸出。
解題思路
首先計算兩個飛機到達機場所需的時間。到達時間等於距離除以速度。比較兩個時間，判斷誰先到達，並輸出相應的訊息。然後計算兩個到達時間的平均值，並將其簡化為最簡分數的形式。簡化分數的過程使用最大公約數 (GCD) 來完成。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
long long a,b,c,d,ca,g;
long long gcd(long long x,long long y){
if( y==0 )return x;
return gcd( y, x%y );
}
int main(){
while(cin >> a >> b >> c >> d){
if(a+b+c+d==0)break;
b*=c;
d*=a;
a*=c;
cout << "Case #" << ++ca << ": " << ((b>d)?"No beer for the captain.":"You owe me a beer!");
g=gcd(a*=2,b+=d);
b/=g;
a/=g;
cout << "\nAvg. arrival time: ";
(b%a)?cout << b << "/" << a << "\n":cout << b/a << "\n";
}
}