第七届年蓝桥杯省赛CC++ A组 最大比例

题目

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。 并且，相邻的两个级别间的比例是个固定值。 也就是说：所有级别的奖金数构成了一个等比数列。比如： 16,24,36,54 其等比值为：3/2 现在，我们随机调查了一些获奖者的奖金数。 请你据此推算可能的最大的等比值。

输入格式： 第一行为数字N(n<100)，表示接下的一行包含N个正整数 第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额 要求输出： 一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数 测试数据保证了输入格式正确，并且最大比例是存在的。

例如，输入： 3 1250 200 32 程序应该输出： 25/4 再例如，输入： 4 3125 32 32 200 程序应该输出： 5/2 再例如，输入： 3 549755813888 524288 2 程序应该输出： 4/1

资源约定： 峰值内存消耗 < 256M CPU消耗 < 3000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。 提交时，注意选择所期望的编译器类型。

思路

思路都在注释里，按计算机的运行步骤从main开始你会看懂的。

代码

#include<stdio.h> #include<stdlib.h> long long num[101],temp1; int yon=0,yonPrintf=0; int cmp(const void *a,const void *b)//基本快速排序,之前测试时用的，但是这题没有使用这个 { return *(long long *)a-*(long long *)b; } void f(int z,int m,int min,int max)//用于判断不同比例（z/m）是否为正确比例 { long long temp=num[0]; for(int i=1;;i++){ if(temp*z/m==num[min+1]||temp==num[min+1]){//如果当前的temp值乘以比例（z/m）等于下一个数字的值或者temp等于下一个数字的值则min加一判断下下个数字的值 min++; if(max==min){ yon++; yonPrintf=1; return ; } }else{ if(temp*z/m>num[min+1]){//如果当前的值乘以给出的比例大于数字的值则此比列不是我们想要的 yonPrintf=-1; return ; }else{ temp=temp*z/m;//如果没有大于继续乘以比例（z/m） //num[min+2]; //num[min+3]; } } } } int main() { int m,numerator,denominator,nu,de; scanf("%d",&m); //输入个数 for(int i=0;i<m;i++){ scanf("%lld",&num[i]); //输入数字储存在num数组中 } for(int i=0;i<m-1;i++){//冒泡排序，对输入的数组进行升序排列 for(int j=0;j<m-i-1;j++){ if(num[j]>num[j+1]){ temp1=num[j]; num[j]=num[j+1]; num[j+1]=temp1; } } } // qsort(num,m,sizeof(num[0]),cmp);//也可用这函数排序，但数字较大不行，上网查了一下还是不行，求大神指点 for(int k=1;;k++){//k代表分子 if(yon==1) break; for(int i=1;i<k;i++){//i代表分母 if(yon==1) break; if(k==i||(k%i==0&&i!=1)||(i%k==0&&k!=1)||k<i){//丢弃比例为小于等于1和不是互质的数 continue; }else{ f(k,i,0,m-1); if(yon==1){ numerator=k; denominator=i; } } } } for(;;){//此循环用于判断比例分数同时平方时是否可行，可行则输出同时平方的值 nu=numerator*numerator; de=denominator*denominator; f(nu,de,0,m-1); if(yonPrintf==-1){ break; }else{ numerator=nu; denominator=de; } } printf("%d/%d",numerator,denominator);//输出 return 0; }

我不是大神，如有不对之处请指点。