ABC143 D - Triangles（二分）

题意：

给定n根木棍，第i根的长度为a(i)，
现在要从中取出三根木棍组成三角形，问有多少种不同的取法。

数据范围：n<=2e3，a(i)<=1e3

解法：

考虑三角形的三条边为A,B,C，A<=B<=C，那么只需要A+B>C就满足组成三角形的条件。
对数组从小到大排序，枚举A和B，二分计算出C的个数即可。

code：

#include<bits/stdc++.h>
using namespace std;
const int maxm=2e3+5;
int a[maxm];
int n;
signed main(){
    cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);int ans=0;for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
    int l=j+1,r=n;int pos=-1;while(l<=r){
    int mid=(l+r)/2;if(a[mid]<a[i]+a[j])pos=mid,l=mid+1;else r=mid-1;}if(pos!=-1)ans+=pos-j;}}cout<<ans<<endl;return 0;
}