本文主要是介绍lightoj 1307 Counting Triangles | 二分/暴力，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你N条边，问你能组成三角形的方法数。
思路：
判断三条边能否组成三角形，根据任意两条边的和大于第三边。
实际上，在确定A<=B<=C的情况下，只要A+B的和大于C即可认为ABC能组成三角形。
这题可以不用二分，用二分速度反而变慢了。排好序后乱搞就可以了。
AC代码：
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int MAXN = 2005;
int a[MAXN];
int main()
{ios::sync_with_stdio(false);int T, cas = 0;int n;cin>>T;while(T--){cin>>n;for(int i = 0;i < n; i++)cin>>a[i];//sort(a, a+n);long long cot = 0;for(int i = 0;i < n-2; i++){int k = i;for(int j = i+1;j < n-1; j++){while(k < n && a[i] + a[j] > a[k])k++;cot += k-j-1;}}cout<<"Case "<<++cas<<": "<<cot<<endl;}return 0;
}这篇关于lightoj 1307 Counting Triangles | 二分/暴力的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
