ACM 已知一些棍子长度,求组成的三角形周长最大为多少?(求O(nlogn)的算法)

sueyurto 1年前 已收到1个回答 举报

岩美 春芽

共回答了16个问题采纳率:87.5% 举报

不知道题目是否允许两根短棍子连接在一起组成一根长棍子?


如果不允许,那么
按照棍子长度从大到小排序,O(nlogn)
令 i=0
i=i+1
若i+2>n,那么组不成三角形,跳第7步
如果第i根 i+1根 i+2根不能够组成三角形,则跳第3步

输出周长,结束
输出不能组成三角形,结束
2-6/7是O(n),总算法复杂度 O(nlogn)

1年前

4
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 2.010 s. - webmaster@yulucn.com