当前位置: 首页> 文旅> 文化 > 石家庄优化_3d建模软件手机版下载_福州seo推广_百度竞价推广流程

石家庄优化_3d建模软件手机版下载_福州seo推广_百度竞价推广流程

时间:2025/7/11 23:05:32来源:https://blog.csdn.net/wuqingshun314159/article/details/147466169 浏览次数:0次
石家庄优化_3d建模软件手机版下载_福州seo推广_百度竞价推广流程

最大比例

原题目链接

题目描述

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

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

例如:
奖金数列为 16, 24, 36, 54,其等比值为 3/23/23/2

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


输入描述

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

输出描述

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

输入样例

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

思路解析

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

关键字:石家庄优化_3d建模软件手机版下载_福州seo推广_百度竞价推广流程

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: