讨论 / 对有序排列贪心的C语言算法
零时迷子 2011-11-03 06:04:00
点我顶贴 收藏 删除
测试结果1: 通过本测试点|有效耗时93ms

测试结果2: 通过本测试点|有效耗时63ms

测试结果3: 通过本测试点|有效耗时141ms

测试结果4: 通过本测试点|有效耗时125ms

测试结果5: 通过本测试点|有效耗时125ms

提交代码: view sourceprint?#include<stdio.h>

#include<math.h>

int check(int k);

int main()

{int n,a[100001]={0},sum=0,i,j,t;

scanf("%d\n",&n);

for(i=1;i<=n;i++)

scanf("%d\n",&a[i]);

for(i=1;i<=n;i++)

for(j=i+1;j<=n;j++)

{if(a[i]<a[j])

{t=a[i];

a[i]=a[j];

a[j]=t;}}

sum=sum+a[n];

while(n!=1)

{sum=sum+a[n]+a[n-1];

t=a[n]+a[n-1];

for(i=1;i<=n-2;i++)

if(t>a[i])

break;

for(j=n-1;j>=i+1;j--)

a[j]=a[j-1];

a[i]=t;

n--;}

printf("%d\n",sum);

if(check(sum)==1)

printf("Yes");

else

printf("No");

return 0;}

int check(int k)

{int s,result=1,i;

s=sqrt(k);

for(i=2;i<=s;i++)

if(k%i==0)

{result=0;

break;}

return result;

}

第一次排序后每次只取最后2个数组元素相加并把新元素插回数组中,数组长度-1直到数组长度为1

查看更多回复
提交回复