题解：P11951 [科大国创杯初中组 2023] 数数

2023z · 2025-03-22 13:23:23 · 题解

这里提供比较暴力的二分做法

前置芝士：lower_bound 函数，它可以计算第一个大于等于 x 的位置。建议先学会二分的原理和手打二分模板很熟练后再用函数。

题意

让我们找出所有满足三根木棍能组成三角形的方案数，条件是两个短边的和大于长边。

思路

我们可以枚举两个短边，用二分计算出第一个大于等于 a_i+a_j 的位置，那这两条短边的方案数就是 pos-j-1 ，累加上方案，最后就是一共的方案数了。

手打二分代码：

#include<bits/stdc++.h>
using namespace std;
long long n,a[8010],ans; //不开 long long 见祖宗
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]; //输入
    sort(a+1,a+n+1); //排序
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int l=j,r=n,mid; //l 表示左端点，r 表示右端点，mid 表示中间位置
            while(l<=r){
                mid=(l+r)>>1;
                if(a[mid]>=a[i]+a[j]) r=mid-1; //如果 a[i]+a[j]<a[mid] 就缩小 r 的范围
                else l=mid+1; //mid+1 为第一个最后一个小于 a[i]+a[j] 的位置的后面一个，也就是第一个大于等于 a[i]+a[j] 的位置
            }
            ans+=l-j-1; //计算方案数，注意要减去 l 自己的位置
        }
    }
    cout<<ans; //输出
    return 0;
}

AC记录

运用函数就方便多了：

#include<bits/stdc++.h>
using namespace std;
long long n,a[8010],ans; //不开 long long 见祖宗
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]; //输入
    sort(a+1,a+n+1); //排序
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int pos=lower_bound(a+1,a+n+1,a[i]+a[j])-a; //计算第一个大于等于 a[i]+a[j] 的位置
            ans+=pos-j-1; //将方案累加
        }
    }
    cout<<ans; //输出
    return 0;
}

还有一个