三角合击题解【C++】

题目描述

兔子军团凭借着独有的三角合击技能，成为了地表最强的军团。
免子军团共有 N 名士兵，每位士兵都有一把刃长为 Li 的佩剑，如果三位士兵的佩剑刃长能组成一个三角形，则说明其属性相符，则这三位士兵可以合力使出一次三角合击，击退敌军。
兔子军团的司令小喵正在检阅这支军团，他想知道，如果任意的三位士兵只能组合一次，军团能使出多少次三角合击？

输入格式

共两行：
第一行一个整数 N ，表示军团的士兵数量；
第二行 N 个整数瓜，依次表示第 i 位士兵佩剑的刃长。

输出格式

一行一个整数，输出三角合击的次数。

样例输入1

3
4 2 3

样例输出1

1

样例1解析

第 1,2,3 位士兵的佩剑组成边长为 {4,2,3} 的三角形，能使出 1 次三角合击。

样例输入2

7
218 786 704 233 645 728 389

样例输出2

23

数据范围

对于 40% 的数据： 3 ≤ N ≤ 100 ; 1 ≤  ≤  ; 
对于 100% 的数据： 3 ≤ N ≤ 2 x  ;  1 ≤  ≤  

解法分析

枚举 + 二分查找：

朴素做法的时间复杂度为 ，观察数据范围显然不能通过。

根据三角形的形成规则来优化求解过程，枚举三角形的两边  和  ，显然第三边  的取值范围为 。二分找到区间的左端点  和右端点 ，特判一下小于  的情况，然后将贡献计入答案中。

输出时需注意除以 3 去掉重复方案，时间复杂度优化至 。

参考代码

#include 
#define ll long long
using namespace std;
ll n, a, x, y, len,ans;
vector l;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++){
    cin >> a;
    l.push_back(a);
    }
    sort(l.begin(), l.end());
    for(int i = 0; i < n;i++){
        for(int j = i + 1; j < n; j++){
            x = l[i], y = l[j];
            auto st = upper_bound(l.begin(), l.end(), abs(x - y));
            auto ed = lower_bound(l.begin(), l.end(), (x + y));
            len = ed - st;
            if(abs(x - y) < x) len--;
            if(abs(x - y) < y) len--;
            if(len > 0) ans += len;
        }
    }
    ans /= 3;
    cout << ans << endl;
    return 0;
}