2020520 PTA钻石争霸赛 T8

当时怎么就没想到这个做法呢？
首先我们枚举每一条边，作为三角形的第二条边，然后二分去找三角形的第三条边，由三角形两边之和大于第三边以及三角形两边之差小于第三边，我们可以确定一个取数范围，统计一下就可以了。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<cmath>
#include<map> 
#include<string>
#include<queue>
#include<stack> 
#include<bitset>
#include<list>
#define IO ios::sync_with_stdio(false)
#define int long long
using namespace std;
int n,p,a[100005],ans;
signed main()
{
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		int r=lower_bound(a+1,a+n+1,a[i]+p)-a;
		int l=upper_bound(a+1,a+n+1,abs(a[i]-p))-a;
		ans+=max((int)0,r-l-(l<=i&&r>=i));//r-l其实是由r-1+l+1得到的，要减去的数是防止自己本身在统计范围以内
	}
	cout<<ans/2;//这种做法每一种三角形都会计算两遍，例如我取了2 3后面又会取3 2
}

本文地址：https://blog.csdn.net/qq_37073764/article/details/107877027