标题:可以帮忙优化一下代码么?能使时间缩短点??具体怎么操作呢?请看看我写的 ...
只看楼主
linxwu
Rank: 1
等 级:新手上路
帖 子:21
专家分:2
注 册:2014-2-28
结帖率:25%
已结贴  问题点数:10 回复次数:10 
可以帮忙优化一下代码么?能使时间缩短点??具体怎么操作呢?请看看我写的代码吧,谢谢
/*描述:输入多条边长n,输出能拼成周长
最大的三角形的周长(若不存在输出-1)*/
#include <stdio.h>
int main()
{
    int a,b,c,d,n;
    int i,j,k,result=-1,x[100000];
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&x[i]);
    for(i=0;i<n-2;i++)
        for(j=i+1;j<n-1;j++)
            for(k=j+1;k<n;k++)
            {
                a=x[i];b=x[j];c=x[k];
                if(a+b>c && a+c>b && b+c>a)
                {
                    if(result<a+b+c);//若周长更大,更新resul的值
                        result=a+b+c;
                }   
            }
    printf("%d\n",result);

    return 0;
}
搜索更多相关主题的帖子: include result 三角形 最大的 
2014-05-11 09:31
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
得分:2 
用选择或者堆先选出最大数 a,次大的 b 和第三大的 c 如果 a - b < c 直接输出,否则a=b,b=c,再找第四个数做新的 c 这样一直循环。


[fly]存在即是合理[/fly]
2014-05-11 11:10
top398
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:427
专家分:857
注 册:2014-5-2
得分:2 
2楼意思是先对所有边长从大到小排序,再依次选取第
0,1,2
1,2,3
2,3,4
....
的边长作为a,b,c
因为 a>b>c
因此只要 b+c>a,则能组成周长最大的三角形。
2014-05-11 11:51
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
得分:0 
以下是引用top398在2014-5-11 11:51:28的发言:

2楼意思是先对所有边长从大到小排序,再依次选取第
0,1,2
1,2,3
2,3,4
....
的边长作为a,b,c
因为 a>b>c
因此只要 b+c>a,则能组成周长最大的三角形。



不是对所有,只选 3 个最大的出来 O(3n)


[fly]存在即是合理[/fly]
2014-05-11 11:58
top398
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:427
专家分:857
注 册:2014-5-2
得分:0 
以下是引用azzbcc在2014-5-11 11:58:52的发言:

 
 
 
不是对所有,只选 3 个最大的出来 O(3n)
当然我可能少补充了一句:找到第一个三角形后就停止。
2014-05-11 12:02
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
得分:0 
好吧我再说一遍,不用把全部数据都排好序。只要找到 3个最大的数,即选择排序外部只做 3 次循环,O(3n)


[fly]存在即是合理[/fly]
2014-05-11 12:16
top398
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:427
专家分:857
注 册:2014-5-2
得分:0 
以下是引用azzbcc在2014-5-11 12:16:47的发言:

好吧我再说一遍,不用把全部数据都排好序。只要找到 3个最大的数,即选择排序外部只做 3 次循环,O(3n)
嗯,确实也不用全部排序,可以先找出2个最大值,以后每次找一个剩余最大值判断三角形是否成立。
2014-05-11 12:34
fragileeye
Rank: 5Rank: 5
等 级:职业侠客
威 望:2
帖 子:107
专家分:387
注 册:2011-5-21
得分:2 
2L算法nice
2014-05-11 17:25
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
得分:2 
精准

www.qunxingw.wang
2014-05-12 23:23
shuainizaika
Rank: 1
等 级:新手上路
帖 子:5
专家分:2
注 册:2014-5-13
得分:2 
楼主的代码着实麻烦
2014-05-13 07:32



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-431356-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.356271 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved