题解分享
题解分享简介
最大比例(编程题) - 题解
我这个代码在洛谷和c语言网都只有78分, 但是在这里可以AC😄 , 我乱写的代码.... 什么混分中, 正解看不懂
```cpp
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;
int main() {
int n;
scanf("%d", &n);
vector<ll> arr;
set<ll> tmp_set;
for (int i = 0; i < n; ++i) {
ll j;
scanf("%lld", &j);
tmp_set.insert(j);
}
for (ll it : tmp_set) {
arr.push_back(it);
}
// 16 -1.5 (*3 / 2)-> -1.5 (*3 / 2)--> 36 -1.5 (*3 / 2)--> 54
// a b c
// b = q*a, c = p*b
// 公比 = p, q 的 最小公约数
// p = 36 / 16 = 3
// q = 54 / 36 = 1.5
double q = 1e18;
// 32 ->*6-> 200 ->15-> 3125 15/6 -> 5/2
// 2 ->*262,144-> 524288 -> *1,048,576 -> 549755813888 1,048,576/262,144 = 4/1
double p = 0;
for (int i = 1; i < arr.size(); ++i) {
double tmp = (double)arr[i] / arr[i - 1];
q = min(q, tmp);
p = max(p, tmp);
}
double res = p / q;
if (res == 1.0) {
ll gy = __gcd(arr[1], arr[0]);
printf("%lld/%lld\n", arr[1] / gy, arr[0] / gy);
}
else {
ll fm = 1, fz;
while (res - (ll)res >= 1e-6) {
res *= 10;
fm *= 10;
}
fz = res;
ll gy = __gcd(fz, fm);
if (fz / gy)
printf("%lld/%lld\n", fz / gy, fm / gy);
else
printf("0/0\n");
}
/*
2 -> *262,144-> 524288 -> *1,048,576 -> 549755813888 *2 -> x
1,048,576/262,144 = 4/1
4
16 24 36 54
3
16 36 54
6
2 32 8 16 32 128
*/
return 0;
}
```
查看全文
0
0
0
1



