目录
1.题目
1.1题目描述
1.2输入输出格式
1.3数据范围
1.4样例
2.算法标签(tag)
贪心,构造,数学
3.题解
3.1思路
写这种题最关键的是什么?脑子要足够清晰!
我们需要构造的是等腰三角形,那么我们的前提就是必须要有一对长度相等的骨头,我们可以先计算每种骨头都有多少对,然后再看无法组对的骨头该如何使用。
如果我们拥有了一对长度为x的骨头,那么我们就需要一根长度在区间(0,2x)的骨头来作为底边。我们发现,x越小,越不容易找到符合条件的底边,而相对的,对于底边来说,骨头越长就越难与其他的腰构成三角形。
因此,我们就要从小到大枚举成对的腰,然后每次贪心地去找到可以组成三角形的无法配对的骨头中长度最长的那一根,这样就可以把条件苛刻的先用掉,最大地可能将所有孤立的骨头用到。
这样下来,可以组成三角形的骨头就只剩下成对的骨头之间了。在这种情况下,假如腰的长度是x,由于需要的底边是(0,2x),长度小于等于x的边必然可以与之构成等腰三角形,那么,我们就只需要贪心地从最长骨头开始找底边,不断将比他长度比他小的骨头拆出来,就一定可以构成等腰三角形,实现构造数量的最大化。最终构造出来的等腰三角形的个数便是: (成对的骨头数量之和)/3。