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