小 b 有一个仅包含非负整数的数组 a, 她想知道有多少个三元组 (i,j,k), 满足 i<j<k 且 a[i],a[j],a[k] 可能作为某个三角形的三条边的边长.
收起
输入
第一行输入一个正整数 n, 表示数组 a 中元素个数;
第二行 n 个非负整数, 表示 a 中元素, 以空格隔开;
其中 0<n≤1000,a 中任意元素 a[i]满足 0≤a[i]≤1000.
输出
输出一个数, 表示满足题意的三元组个数
输入样例
4 2 2 3 4
输出样例
3
很容易想到一个 O(n^2 * logn)的解法, 我们将原来数组排完序后, 枚举两个较小的边, 然后二分出最长边的范围即可;
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstdlib>
- #include<set>
- #include<map>
- using namespace std;
- #define maxn 100005
- #define rdint(x) scanf("%d",&x)
- typedef long long ll;
- int n;
- int a[1002];
- int main() {
- rdint(n);
- for (int i = 1; i <= n; i++)rdint(a[i]);
- int tot = 0;
- sort(a + 1, a + 1 + n);
- // int nn = unique(a + 1, a + 1 + n) - (a + 1);
- for (int i = 1; i <n; i++) {
- for (int j = i + 1; j < n; j++) {
- int l = j + 1;
- int r = n;
- int ans1 = -1;
- while (l <= r) {
- int mid = (l + r) / 2;
- if (a[mid]> (a[j] - a[i])) {
- r = mid - 1; ans1 = mid;
- }
- else {
- l = mid + 1;
- }
- }
- ans1 = upper_bound(a + 1 + j + 1, a + 1 + n, a[j] - a[i]) - (a + 1);
- l = j + 1; r = n;
- int ans2 = -1;
- ans2 = lower_bound(a + 1 + j + 1, a + 1 + n, a[i] + a[j]) - (a + 1);
- // cout <<ans1 << '' << ans2 <<' '<< a[i] + a[j] << endl;
- if (ans1 == -1 || ans2 == -1)continue;
- // tot += (ans2 - ans1 + 1);
- else if (ans2 == ans1 && a[ans1]> a[i] + a[j]) {
- tot += 0;
- }
- else if (ans2 == ans1 && a[ans2] <a[i] + a[j]) {
- // cout << 2 << endl;
- tot += (ans2 - ans1 + 1);
- }
- else if (ans2> ans1 && a[ans2]<a[i]+a[j]) {
- tot += (ans2 - ans1 + 1);
- }
- else if (ans2> ans1&& a[ans2]>= a[i] + a[j]) {
- tot += (ans2 - ans1);
- }
- }
- }
- printf("%d\n", tot);
- // system("pause");
- }
来源: http://www.bubuko.com/infodetail-3110207.html