自动搬运

查看原文

来自洛谷，原作者为

	2023z 乘风破浪向朝阳，披荆斩棘露锋芒

搬运于2025-08-24 23:11:35，当前版本为作者最后更新于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;
}

还有一个