合肥 做网站,深圳龙华区教师招聘,网站开发竞价单页,wordpress商城 小程序题目描述#xff1a; X星球的某个大奖赛设了 M 级奖励。 每个级别的奖金是一个正整数。 并且#xff0c;相邻的两个级别间的比例是个固定值。 也就是说#xff1a;所有级别的奖金数构成了一个等比数列。 比如#xff1a;16,24,36,54#xff0c;其等比值为#xff1a;3/2。… 题目描述 X星球的某个大奖赛设了 M 级奖励。 每个级别的奖金是一个正整数。 并且相邻的两个级别间的比例是个固定值。 也就是说所有级别的奖金数构成了一个等比数列。 比如16,24,36,54其等比值为3/2。 现在我们随机调查了一些获奖者的奖金数。 请你据此推算可能的最大的等比值。 输入格式 第一行为数字 N 表示接下的一行包含 N 个正整数。 第二行 N 个正整数 Xi用空格分开每个整数表示调查到的某人的奖金数额。 输出格式 一个形如 A/B 的分数要求 A、B 互质表示可能的最大比例系数。 数据范围 0N100 0Xi10^9 数据保证一定有解。 输入样例1 3 1250 200 32 输出样例1 25/4 这道题做的时候可以气死我为什么呢首先我觉得它的范围有问题就是这里的Xi它说小于10的九次方所以用int也不会超的吧没想到他还真超了呢我看了很多遍代码都没看见什么乘法和加法能让一个数超int的然后我去看别人的博客发现XX的别的博客给的Xi范围是10^12不会蓝桥云课刷题那里写少了吧气死我了我真的真的改了很久的代码
然后第二个气人的点是这道题没卡测试点所以直接用gcd求出相邻两数的互质比值找出整个范围最小的那个就可以了这样好像也可以过不过怎么会这样子比如说三个奖励1 4 32最大合适的比例应该是2/1而不是4/1我看见有个人的代码结果是4/1也能对就是好像蓝桥云课刷题那里拿的测试点太低端了卡不了代码气死我了测试点都不好好弄一下
接下来说思路要想找到最小比例得用指数的更相减损术可以看一下另一个博客
http://t.csdnimg.cn/NPZtY
有了这个代码就好写了哦对记得审题题目可能有重复的奖金因为有不同的人可能拿同一类奖金这个要筛掉不然会出问题的
ac代码如下
#includebits/stdc.h
using namespace std;
const int N1e210;
#define ll long long
ll x[N],temp[N];
ll a,b;
ll gcd_sub(ll x1,ll x2) { if(x1x2)swap(x1,x2);//保证x1比x2大 if(x21)return x1;return gcd_sub(x2,x1/x2);
}
int main() {int n;cinn;for(int i0; in; i)cintemp[i];int len0;sort(temp,tempn);x[len]temp[0];for(int i1;in;i){if(temp[i]!temp[i-1])x[len]temp[i];}if(len1) {printf(%ld/1,x[0]);} else {ax[1]/__gcd(x[0],x[1]),bx[0]/__gcd(x[0],x[1]);for(int i2; ilen; i) {ll d__gcd(x[i],x[i-1]);agcd_sub(a,x[i]/d);bgcd_sub(b,x[i-1]/d);}printf(%ld/%ld,a,b);}return 0;
}
