给你N个数字，从其中选出三个数字来构成某个三角形的三个边 问有多少种合理的取法c++

Question

Description
给你N个数字，从其中选出三个数字来构成某个三角形的三个边 问有多少种合理的取法(用c++)

Format
Input
第一行给出N

接下来给出N个数字

3≤N≤2×10^3

1≤L i≤10 ^3

Output
如题

Samples
输入数据 1
7
218 786 704 233 645 728 389

输出数据 1
23

输入数据 2
4
1 2 3 4

输出数据 2
1

Answer 1

先dfs找三元组，然后判断，时间复杂度O(N^3)
注意最后要去重/6

#include<bits/stdc++.h>
using namespace std;
int ans=0,a[2009],n,c[4];    //c表示被选的数的编号
                            //三角形判定：任意两边之和大于第三边 
void dfs(int x,int id){        //x表示当前正在枚举的数是三角形三边的哪一个
                            //id表示选用a数组的第几个 
                            //由于第1个数有n种情况，所以要在main函数里调用dfs(1,i)n次 
    c[x]=id;//记录使用
    if(x==3) {//选满3个 
        if(a[c[1]]+a[c[2]]>a[c[3]]&&a[c[1]]+a[c[3]]>a[c[2]]&&a[c[2]]+a[c[3]]>a[c[1]])//是三角形 
            ans++;
        c[x]=0;//退回，要清除记录
        return;//退回 
    }
    for(int i=1;i<=n;i++)//循环遍历查找 
        if(i!=c[1]&&i!=c[2]&&i!=c[3])//没有出现过
            dfs(x+1,i);//继续调用 
    c[x]=0;//退回，要清除记录    
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)dfs(1,i);
    cout<<ans/6;//去重，三元组可以有3*2*1=6种不同方法，要算同一种 
    return 0; 
}