1207 - 数三角形


作为三角形的边长,要求两边之和大于第三边。因此暴力枚举的复杂度是 O(n^3) 的,即枚举 i,j,k ,然后判断是否合法。

优化:如果我们先将 a 排序,可以只枚举 (i,j) ,然后用二分的方法统计有多少符合条件的 k ,复杂度降为 O(n2logn)

尺取法优化: 枚举 i ,然后用尺取法处理 (j,k),可以 O(n)统计有多少对符合条件的 (j,k) ,这样复杂度将为了 O(n^2)