P11951 [科大国创杯初中组 2023] 数数

P11951 [科大国创杯初中组 2023] 数数

▍题意

给定 $n$ 根木棍，第 $i$ 根木棍的长度为 $a_i$。求有多少种选三根木棍的方案，使得这三根木棍能组成一个三角形。组成三角形的条件是：较短的两根木棍长度和大于最长的那根木棍长度。

数据范围：$3\le n\le 8\times 10^3$，$1\le a_i\le 10^9$。

▍分析

形成三角形条件：三角形三条边对应所在的位置 $(i,j,k)$ 满足位置关系 $(i<j<k)$，$a_i+a_j>a_k$。

通过枚举 $i,j$ 位置，利用二分快速定位 $k$，$k$ 满足 ($k>j$) 且定位是可以通过 lower_bound 快速定位首个 $ \ge a_i+a_j$ 的位置 $p$，而 $p-1$ 即为最后一个满足的 $k$ 位置，则贡献的位置就是 k = [j+1,j+2,...p-1],

cnt+=(p-1)-(j+1)+1。

举个例子：

2  2  3  3  5
i  j  k1 k2 p
(i,j,k1)
(i,j,k2)

其中 $(2,2,3),(2,2,3)$ 都满足三角形的条件，而贡献的位置 $[p-1,j+1]$ 就是 $(p-1)-(j+1)+1$。

时间复杂度：枚举两条边 $n^2$，二分查找 $logn$，总时间复杂度：$n^{2}logn$。

▍参考代码(1)

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

const int N = 8005;
int a[N];
ll n, ans;

/* n^2logn 做法 */

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + n); /* 满足单调性(有序) nlogn */
    /* 枚举前两个木棍，通过二分快速定位第三根木棍，计算贡献。n^2logn */
    for (int i = 1; i <= n - 2; i++)
        for (int j = i + 1; j <= n - 1; j++)
        {
            int p = lower_bound(a + 1, a + 1 + n, a[i] + a[j]) - (a + 1);
            int k = j + 1;
            ans += (p - k + 1);
        }

    cout << ans << "\n";
    return 0;
}

[!TIP]

虽然能通过本题（因为数据太水），实际上极限能超过 $1s$ 的运算量。

思考如何优化这个算法？

提示可以通过三角形构成条件的式子入手优化！

▍优化做法分析

1. 排序优化：首先将所有木棍按长度升序排序，便于后续处理。
2. 双指针法：对于每根木棍 $a_i$ 作为最长边时，在其左侧使用双指针 $l$ 和 $r$ 寻找满足 $a_l+a_r>a_i$ 的木棍对。若满足条件，则 $l$ 到 $r-1$ 之间的所有木棍与 $r$ 的组合均合法，统计这些组合数后移动指针。
3. 时间复杂度：排序为 $O(n\log n)$，双指针部分为 $O(n^2)$，总复杂度为 $O(n^2)$，可通过题目数据规模。

▍参考代码(2)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 8001;
int n, a[N], ans;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 3; i <= n; i++) {
        int l = 1, r = i - 1, cnt = 0;
        while (l < r) {
            if (a[l] + a[r] > a[i]) {
                cnt += r - l;
                r--;
            } else l++;
        }
        ans += cnt;
    }
    cout << ans;
}

优化后的运行效率对比如下：