原题链接
不一样的思路
其实这题我当时A掉后感觉略难，后来看解说发现自己的思路复杂了，但是计算复杂度比答案的小（答案用的暴捜加二分探索），在这里分享一下。
算法：
开一个数组用来统计长度为
的木棒的个数
，并算其前缀和
，然后遍历计算。
遍历的时候先固定两个木棒，然后算最大第三木棒长度和最小第三木棒长度。对前缀和做差计算这之间数值的个数，加到答案里。若跟固定的两个木棒重复，就把刚刚的数-1或-2 。
注意
重复情况的计算：因为上述结果每组三角形会重复出现3次，上述答案要
#include<bits/stdc++.h>
using namespace std;
//省略一些宏
//---------------------
#define MAXN 2005
//---------------------
ll n;
ll l[MAXN];
int main(){
cin >> n;
REP(i,n) cin >> l[i];
sort(l,l+n);
ll sl[MAXN];
ZERO(sl);
REP(i,n) sl[l[i]]++;
ll sum[MAXN+1];
TOSUM(sl,sum,MAXN+1);
ll ans = 0;
REP(i,n-1) FOR(j,i+1,n)
{
ll up = l[i]+l[j]-1,low = (ll)abs(l[i]-l[j])+1;
ans += sum[up]-sum[low-1];
if(l[i]>=low && l[i] <= up) ans--;
if(l[j]>=low && l[j] <= up) ans--;
}
PRT(ans/3);
return 0;
}
