ABC143 D Triangles 快乐三角形数一数

原题链接

不一样的思路

其实这题我当时A掉后感觉略难，后来看解说发现自己的思路复杂了，但是计算复杂度比答案的$O(N^2\log N)$小（答案用的暴捜加二分探索），在这里分享一下。

$O(N^2)$算法：
开一个数组$C_n$用来统计长度为$n$的木棒的个数$O(N)$，并算其前缀和$O(N)$，然后遍历计算。
遍历的时候先固定两个木棒，然后算最大第三木棒长度和最小第三木棒长度。对前缀和做差计算这之间数值的个数，加到答案里。若跟固定的两个木棒重复，就把刚刚的数-1或-2 。

注意

重复情况的计算：因为上述结果每组三角形会重复出现3次，上述答案要$÷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;
}