本文主要是介绍数列极差问题（贪心） 求数据（一直Wrong），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*日期：2011-10-21作者：xiaosi
题目: 数列极差问题（贪心）
*/
#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define Maxint 999999
#define Minint -1
int progression[2001];
int progression1[2001];
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int Max(int progression[],int n)
{
int i,j,a,b,max;
for(i=0;i<n-1;i++)//求max
{
a=0;b=1;
for(j=2;j<n;j++)
{
if(progression[j]<progression[a]||progression[j]<progression[b])
{
if(progression[a]>progression[b])
{
a=j;
}
else
{
b=j;
}
}
}
max=progression[a]*progression[b]+1;
progression[a]=max;
progression[b]=Maxint;
}
return max;
}
int Min(int progression[],int n)
{
int i,j,a,b,min;
for(i=n-2;i>=0;i--)//求min
{
a=n-2;b=n-1;
for(j=n-3;j>=0;j--)
{
if(progression[j]>progression[a]||progression[j]>progression[b])
{
if(progression[a]<progression[b])
{
a=j;
}
else
{
b=j;
}
}
}
min=progression[a]*progression[b]+1;
progression[a]=min;
progression[b]=Minint;
}
return min;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int min,max,M,num,i,j;
for(i=0;i<n;i++)
{
scanf("%d",&progression[i]);
}
qsort(progression,n,sizeof(progression[0]),cmp);
for(i=0;i<n;i++)
{
progression1[i]=progression[i];
}
max=Max(progression,n);
//min=Min(progression1,n);
min=1;
for(i=n-1;i>=0;i--)
{
min=min*progression1[i]+1;
}
M=max-min;
if(M==0)
{
num=1;
}
else
{
num=(int)log10(M)+1;
}
printf("%d\n%d\n",num,M);
}
return 0;
}
这篇关于数列极差问题（贪心） 求数据（一直Wrong）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
