前缀和、双指针

时间复杂度O(n^2)

萌新没怎么写过题解 可能逻辑表达混乱

鼓捣了俩小时终于AC了，大致思路是分别统计等边三角形、等腰三角形、其他三角形 对于非退化三角形的判断: 不需要分别判断 x+y<z x+z<y y+z<x 只需要保证 x<=y<=z x+y<z即可

等边三角形只需要判断木棍数量>=3就好了

  for (int i=1;i<=n;i++) {
    if (a[i].val>=3) sum++;
  }

等腰三角形的思路是先找数量多于2的木棍当作三角形的腰，然后用统计是否能组成非退化三角形

用一层循环遍历一遍满足可组成三角形腰的木棍(即数量>=2)，然后开始在合法木棍左右两侧寻找满足第三条的边 如果第三条边在左侧(小)则所有木棍都符合 如果第三条边在右侧(大)则需要判断 因为len数组是先排序后构造的，固然有序，所以直接用了lower_bound，直接寻找第一个大于等于腰长度两倍的木棍(x+y<z)，这个木棍及其后面的木棍均无法符合组成三角形的要求

        for (int i=1;i<=n;i++) {
            if (a[i].val<2) continue;
            sum+=pre[i-1];
            ll it=lower_bound(len.begin()+1,len.begin()+n+1,a[i].len*2)-len.begin();
            sum+=pre[it-1]-pre[i];
        }

其他三角形(三条边均不一样长) 使用双指针从O(n^3)降到了O(n^2) 遍历i从1到n 用滑动窗口在i左侧反复寻找组成三角形最小的j和右侧最大的k 在j层循环遍历时每找到一个k用前缀和加到总和，就是符合组成三角形的数量

        for (int i=1;i<=n;i++) {
            int k=i+1;
            for (int j=1;j<i;j++) {
                while (k<=n&&a[i].len+a[j].len>a[k].len) {
                    k++;
                }
                sum+=pre[k-1]-pre[i];
            }
        }

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5010;
struct node {
    int len;
    int val;
};
bool cmp(node x,node y) {
    if (x.len<y.len) return true;
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;cin>>t;
    while (t--) {
        int n;cin>>n;
        node a[N];
        for (int i=1;i<=n;i++) {
            cin>>a[i].len>>a[i].val;
        }
        sort(a+1,a+n+1,cmp);
        ll sum=0;
        vector<int>len(n+1,0);
        vector<int>pre(n+1,0);
        //构造前缀和数组与len数组
        for (int i=1;i<=n;i++) {
            if (a[i].val>=1) pre[i]++;
            pre[i]+=pre[i-1];
            len[i]=a[i].len;
        }
        //寻找等边三角形
        for (int i=1;i<=n;i++) {
            if (a[i].val>=3) sum++;
        }
        //寻找等腰三角形
        for (int i=1;i<=n;i++) {
            if (a[i].val<2) continue;
            sum+=pre[i-1];
            ll it=lower_bound(len.begin()+1,len.begin()+n+1,a[i].len*2)-len.begin();
            sum+=pre[it-1]-pre[i];
        }
        //寻找其他三角形
        for (int i=1;i<=n;i++) {
            int k=i+1;
            for (int j=1;j<i;j++) {
                while (k<=n&&a[i].len+a[j].len>a[k].len) {
                    k++;
                }
                sum+=pre[k-1]-pre[i];
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}