Triangular Collection思维

题目描述

Call a set of positive integers triangular if it has size at least three and, for all triples of distinct integers from the set, a triangle with those three integers as side lengths can be constructed.

Given a set of positive integers, compute the number of its triangular subsets.

输入

The first line of input contains a single integer n (1 ≤ n ≤ 50), which is the number of integers in the set.

Each of the the next n lines contains a single integer x (1 ≤ x ≤ 109 ). These are the elements of the set. They are guaranteed to be distinct.

输出

Output a single integer, which is the number of triangular subsets of the given set.

样例输入 Copy

【样例1】

5
3
1
5
9
10

【样例2】

10
27
26
17
10
2
14
1
12
23
39

样例输出 Copy

【样例1】

2

【样例2】

58

题意：

求出集合的个数，这些集合要满足，在该集合中任意选三个点可以构成三角形

将所有的边长进行按照从小到大进行排序之后，枚举两条边的起点和终点，然后计算出这两条边的和，求出在排序后的数组中在(a[j],sum)之间的能够组成的子集的数量进行计算，对于n个点，有2n - 1种选择方式

int n, m, k;
ll a[maxn];
int main() {
    n = read;
    ll ans = 0;
    for (int i = 1; i <= n; i++) a[i] = read;
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1 + i; j <= n; j++) {
            ll sum = a[i] + a[j];
            int p = n;
            while (a[p] >= sum) p--;
            ans += (1LL << (p - j));
            ans --;
        }
    }
    cout << ans << endl;
    return 0;
}