正经题解｜树枝

提示

三角形的性质：任意两边之和大于第三边 或 较短两条边之和大于最长边。

题目解析

求给定大小为 $n$ 的数组中选择三个元素能够构成一个三角形的方案数。

那么我们需要考虑三角形的性质：任意两边之和大于第三边 或 较短两条边之和大于最长边。

那么一个比较明显的思路是直接三重循环枚举三条边，然后检查即可。
但是这种方法的时间复杂度为 $O(n^3)$。本题 $n(1 \le n \le 5000)$ 显然此种做法无法在时限内通过本题。

那么接下来我们考虑如何优化枚举。
首先考虑真的需要枚举三条边吗？如果我们已经确定了两条较小的边 $i, j$，就可以确定最长的边的大小最大为 $a_i + a_j - 1$。
为了方便我们可以将数组从小到大排序，然后可以使用二分来确定合法最长边在数组中的范围。此做法时间复杂度为 $O(n^2\log{n})$。

由于本题为单测试点多测试用例，$10 \times 5000 \times 5000 \times \log_{2}{5000} \approx 3 \times 10^9$，所以此做法仍然无法通过本题。

本题的数据范围要求时间复杂度在 $O(n^2)$ 及以内的做法，可以考虑把二分优化掉。

在上述枚举两条较短边，再使用二分确定第三条边的做法中，从小到大枚举前两条边，那么他们的长度之和显然是逐渐增大的，确定的两条较小边 $i, j(1 \le i < j + 1 < n)$ ，令数组中 第一个大于等于 $a_i + a_j$ 的元素下标为 $k_j$ ，那么对于边 $i, j + 1$ 令数组中 第一个大于等于 $a_i + a_{j+1}$ 的元素下标为 $k_{j+1}$，那么显然 $k_j \le k_{j+1}$，也就是说第三条边的最大长度是不断变大的。

那么我们便可以不用每次都重复地使用二分来判断最长第三边的位置。而是直接使用一个变量 $k$ 来表示 第一个大于等于 $a_i + a_j$ 的元素在数组中的位置。随着第二条边的长度 $a_j$ 的增大，那么 $k$ 也是不断增大的。这样我们枚举出两条较小边 $i, j$ 后，向后移动 $k$ 直到 $a_i + a_j \ge a_k$，可选的第三条边的数量就是 $k - j - 1$ 。

AC代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        vector<int> a(n);
        for (auto &x : a) cin >> x;
        sort(begin(a), end(a));
        i64 res = 0;
        for (int i = 0; i + 2 < n; ++i)
            for (int j = i + 1, k = i + 2; j + 1 < n; ++j) {
                // 向后移动 k 至当前允许的最长的第三边的位置
                while (k < n and a[i] + a[j] > a[k]) ++k;
                res += k - j - 1;
            }
        cout << res << '\n';
    }
    return 0;
}

复杂度分析

两重循环枚举较小的两条边时间复杂度为 $O(n^2)$ ，第三条边的范围随着第二条边从小到大枚举，也是不断增大的，内层的 while 循环在整个枚举第二条边的过程中最多执行 $n$ 次，所以总的时间复杂度为 $O(n^2)$。