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

· · 题解

题目简述

给定长度为 n 的正整数序列 a，求在 a 中任意选三个数可以分别作为一个三角形的三边并组成三角形的方案个数。

主要思路

首先可以排除 O(n^{3}) 的纯暴力做法。

考虑二分，给定的初数组不一定有序，所以需要先排一遍序。随后用 n^{2} 的方法枚举 i 和 j，满足 i<j 并且 i,j < n；这样剩下一条边的范围是确定的，即 a_{j} \sim a_{i}+a_{j}-1，这里不需要考虑第三条边 < a_{j} 的情况，否则会重复算。用 lower_bound 分别枚举第一个满足 \ge a_{j} 和第一个满足 \ge a_{i}+a_{j} 的元素的下标，答案加上两数相减即可。

时间复杂度

O(n^{2} \log n)

注意事项

在最极端情况下，答案会达到 n^{3}，即 5.12 \times 10^{11}，所以：十年 OI 一场空，_____。

AC Code

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef long double db;
const int N = 8e3 + 10;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------
int a[N];
// ----------------------------

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    // ----------------------------
    ll ans = 0;
    sort(a + 1, a + n + 1);
    for (int i = 1; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            ans += (lower_bound(a + j + 1, a + n + 1, a[i] + a[j]) - a) - (lower_bound(a + j + 1, a + n + 1, a[j]) - a);
        }
    }
    // ----------------------------
    cout << ans;
    return 0;
}