HDU 6601 – Keen On Everything But Triangle

题目链接:HDU 6601

首先可以确定为了在线性时间内判断和获取一个可以形成最大三角形的三元组,我们需要获得的是一个已经排序的序列。

已经从大到小排序的序列,只有$d_i \leq d_{i+1} + d_{i + 2}$的时候不能构成三角形,我们考虑最极端的情况,即$d_i = d_{i+1} + d_{i+2}$,根据斐波那契数列的性质,最多这个数列会在45项内收敛到0。

所以我们只要维护区间前45大的数,然后$O(45)$地判断最大三角形就可以了,这里可以用线段树实现,把push-up操作改成归并即可。

 

说点什么

avatar
50
  Subscribe  
提醒