最大比例
原題目鏈接
題目描述
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
思路解析
貪心做法是，排序+去重后，選擇相鄰兩個數比值最小的。
