JXUST-OJ 2389 拼接三角形（二分+模拟）

题目：给你n个可重复的数让你判断最多能组成几个三角形
分析：分情况等边，等腰，三边不等，用 $a+b>c$a+b>c公式来二分查找边界的c。

c++内置二分查找 https://blog.****.net/GodJing007/article/details/88982000

注：遇到题目累加累乘一定要用long long

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
const int N = 3e3 + 10;
const int M = 1e4 + 10;

int a[N];
map<int, int> m;
int n, num, cnt = 0;
ll ans = 0;

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &num);
        if(!m[num]){
            a[cnt++] = num;
        }
        m[num]++;
    }
    sort(a, a + cnt);
    for(int i = 0; i < cnt; i++){
        if(m[a[i]] >= 3){     //等边三角形
            ans++;
        }      
        if(m[a[i]] >= 2){     //等腰三角形
            int pos = lower_bound(a + i, a + cnt, 2*a[i]) - a;
            ans += (pos - 1);
        }
        for (int j = i + 1; j < cnt; j++){      //普通三角形
            int pos = lower_bound(a + j, a + cnt, a[i] + a[j]) - a;
            ans += (pos - j - 1);
        }
    }
    cout << ans << endl;
    return 0;
}