蓝桥杯 19. 最大比例

最大比例

原题目链接

题目描述

X 星球的某个大奖赛设了 M 级奖励。每个级别的奖金是一个正整数。

并且，相邻两个级别间的比例是一个固定值，也就是说：所有级别的奖金构成一个等比数列。

例如：
奖金数列为 16, 24, 36, 54，其等比值为 3/2、3/2、3/2。

现在，我们随机调查了一些获奖者的奖金数。
请你根据这些数据推算出可能的最大等比值。

---

输入描述

• 第一行：一个整数 N（0 < N < 100），表示接下来有 N 个正整数；
• 第二行：N 个正整数 X₁, X₂, ..., Xₙ（Xᵢ < 10⁹），用空格隔开，表示调查到的某些获奖者的奖金数额。

---

输出描述

• 输出一个形如 A/B 的最简分数，表示可能的最大比例系数，其中 A 和 B 是互质正整数。

---

输入样例

3
1250 200 32

---

输出样例

25/4

c++代码

#include<bits/stdc++.h>using namespace std;typedef long long ll;ll greatest_common_divisor(ll a, ll b) {if (a < b) return greatest_common_divisor(b, a);if (b == 0) return a;else return greatest_common_divisor(b, a % b);
}int main() {ll n, a, maxi, maxj;cin >> n;vector<double> arr;double min_val = DBL_MAX;unordered_set<ll> st;for (ll i = 0; i < n; i++) {cin >> a;if (st.find(a) == st.end()) {st.insert(a);arr.push_back(a);}}sort(arr.begin(), arr.end());for (ll i = 1; i < arr.size(); i++) {if (arr[i] / arr[i - 1] < min_val) {maxi = (ll)arr[i - 1];maxj = (ll)arr[i];min_val = arr[i] / arr[i - 1];}}ll k = greatest_common_divisor(maxi, maxj);cout << maxj / k<< "/" << maxi / k;return 0;
}//by wqs

思路解析

贪心做法是，排序+去重后，选择相邻两个数比值最小的。