AcWing 1223. 最大比例
原题链接
中等
作者:
Nazarena
,
2021-01-15 19:19:11
,
所有人可见
,
阅读 476
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
long long judge(long long min, long long max)
{
while(max % min != 0)
{
long long res = max % min;
max = min;
min = res;
}
return min;
}
int main()
{
int n,m = 0;
long long arr[100],res[2][100];
long long a,b,t; //a分子,b分母
long long product = 1;
long long am,bm;
cin >> n;
for(int i=0;i<n;i++)
cin >> arr[i];
sort(arr, arr + n);
for(int i=1;i<n;i++)
{
a = arr[i-1]; //a小数,b大数
b = arr[i];
if(a != b)
{
t = judge(a,b);
res[1][m] = a / t;
res[0][m] = b / t;
m++;
}
}
for(int i=0;i<m;i++)
product *= res[1][i];
for(int i=0;i<m;i++)
res[0][i] = res[0][i] * product;
am = res[1][0];
bm = res[0][0];
for(int i=1;i<m;i++)
{
if(res[0][i]<bm)
{
am = res[1][i];
bm = res[0][i];
}
}
bm /= product;
cout << bm << "/" << am;
return 0;
}