比赛时，当我看到这道题，我彻底的懵比了，没有思路，没有思路，没有思路，重要的事说三遍，赛后，也没有在网上找别人的代码看，因为对省赛感觉很不好，以为自己挂了，所以没有心情去看题，应该说是不敢去看题，成与败，关系着我的尊严，当初学校不让我报名A组，很多人都嘲讽我不知天高地厚，一个破二本的院校，还想挑战A组；更有人反问我，你才学了几天，到你比赛时撑死了也就学满七个月，就这么瞧不起B组？
实话说，我真的瞧不起B组，因为我相信自己的能力！
废话不多说，转入正题，对于这个题，我真的是没有一丝的思路可言，前天我百度了一下，网上还没有一个这道题相关的问题答案解析，没有办法，只能靠自己了，毕竟自己动手丰衣足食嘛。
先上题：
X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16,24,36,54
其等比值为：3/2
现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
输入格式：
第一行为数字N，表示接下的一行包含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 ， 不能通过工程设置而省略常用头文件。
苦于没有思路，苦于网上没有提示，只能自己想，最后，在一张废纸上找起了规律，结果发现真的毫无规律可言，只能作罢，用最朴素的办法解吧！
逆向思维考虑，需要求最大比例，那么肯定要从比例入手，所以首先就是求出所有的比例，并且去重，然后就需要对这些比例进行排序来谋求最大的基数，这个基数即为最大的比例。
思路听着很简单，但是实现起来着实麻烦，需要考虑的细节问题贼多，不多说了，看代码吧，代码更有说服力！
代码C：
#include <stdio.h>
#include <math.h>
#define _MAX 1000000000000
int N, p = 0;
long long M[100], nAtor[100], dAtor[100];
double W[100];
//M原数据排序去重
void sequenceM()
{
int len = N, i , j;
for (i = 0; i < N - 1; i++)
{
for (j = i + 1; j < N; j++)
{
if (M[i] > M[j])
{
M[i] ^= M[j];
M[j] ^= M[i];
M[i] ^= M[j];
}
else if (M[i] == M[j])
{
M[j] = _MAX;
len--;
}
}
}
N = len;
// for (i = 0; i < N; i++)
// {
// printf("%lld ", M[i]);
// }
// printf("\n");
return ;
}
//约分
void reduce(int i)
{
long long j = M[i];
for (; j > 0; j--)
{
if (M[i] % j == 0 && M[i + 1] % j == 0)
{
dAtor[i] = M[i] / j;
nAtor[i] = M[i + 1] / j;
return ;
}
}
return ;
}
//W数据排序去重
void sequenceW()
{
int len = N - 1, i , j;
for (i = 0; i < N - 2; i++)
{
for (j = i + 1; j < N - 1; j++)
{
if (W[i] > W[j])
{
double tempW = W[i];
W[i] = W[j];
W[j] = tempW;
long long tempN = nAtor[i];
nAtor[i] = nAtor[j];
nAtor[j] = tempN;
long long tempD = dAtor[i];
dAtor[i] = dAtor[j];
dAtor[j] = tempD;
}
else if (W[i] == W[j])
{
W[j] = _MAX;
len--;
}
}
}
N = len;
// for (i = 0; i < N; i++)
// {
// printf("%g %lld %lld\n", W[i], nAtor[i], dAtor[i]);
// }
return ;
}
//分别求分子、分母基数
long long NDbase(long long *Ator)
{
long long flag = Ator[0];
if (N == 1)
{
return flag;
}
int i = 1, j, tag = 0; //标记flag是否为符合基数要求
for (; i < N; i++)
{
for (j = 2; pow((double)flag, (double)j) <= Ator[i]; j++)
{
if (pow((double)flag, (double)j) == Ator[i])
{
tag = 1;
break;
}
}
if (tag == 1)
{
tag = 0;
continue;
}
break;
}
if (i == N)
{
return flag;
}
tag = 0;
for (flag = Ator[0] / 2; flag > 0; flag--)
{
for (i = 0; i < N; i++)
{
for (j = 2; pow((double)flag, (double)j) <= Ator[i]; j++)
{
if (pow((double)flag, (double)j) == Ator[i])
{
tag = 1;
break;
}
}
if (tag == 1)
{
tag = 0;
continue;
}
break;
}
if (i == N)
{
return flag;
}
}
return 0;
}
//求最大基数
void base()
{
long long N, D; //最大比例的分子和分母
N = NDbase(nAtor);
D = NDbase(dAtor);
printf("%lld/%lld\n", N, D);
return ;
}
//求最大比例
void pro()
{
int i;
sequenceM();
for (i = 0; i < N - 1; i++)
{
W[i] = M[i + 1] * 1.0 / M[i];
reduce(i);
}
sequenceW();
base();
return ;
}
int main(int argc, const char * argv[])
{
int i = 0;
scanf("%d", &N);
for (; i < N; i++)
{
scanf("%lld", &M[i]);
}
pro();
return 0;
}
是不是很长啊？不要急，慢慢看吧，注释我也写了，希望你能懂！真不懂的话，就别看了，去做别的题吧！做这个题是在浪费时间，对很多人而言……
OVER！！！
京公网安备 11010502036488号