题目链接： https://www.nowcoder.com/acm/contest/84/F
题目描述
给定n个数，从中选出三个数，使得最大的那个减最小的那个的值小于等于d，问有多少种选法。
输入描述:
第一行两个整数n，d(1 <= n <= 100,000，1 <= d <= 1000,000,000)； 第二行n个整数满足abs(ai) <= 1,000,000,000。数据保证a单调递增。
输出描述:
输出一个整数表示满足条件的选法。
示例1
输入
4 3 1 2 3 4
输出
4
示例2
输入
4 2 -3 -2 -1 0
输出
2
示例3
输入
5 19 1 10 20 30 50
输出
1
题目很清晰。。看见这种题就犯怵。。排列组合学的不好。。但幸好这道提比较简单。。水一水就过去了。。
遍历一边数组，然后对于每个数字，找到最大的符合条件的数字，然后C（2，len）len是有多少个数字（除了第一个数字）
然后就开一个ll的sum把他们都加起来就行了。。
ac：
#include<stdio.h>
#include<string.h>
#include<math.h>
//#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define da 0x3f3f3f3f
#define xiao -0x3f3f3f3f
#define clean(a,b) memset(a,b,sizeof(a))// 水印
ll shuzu[100100];
ll n,d;
int main()
{
cin>>n>>d;
int i,j;
for(i=0;i<n;++i)
cin>>shuzu[i];
ll sum=0;//注意数据范围
for(i=0;i<n;++i)
{
ll l=i,r=n,mid;
while(r-l>1)//二分条件就是两个数紧挨着就结束
{
mid=(l+r)/2;
// cout<<"r:"<<r<<" l:"<<l<<" mid:"<<mid<<endl;
if(shuzu[mid]-shuzu[i]>d)
r=mid;
else
l=mid;
// cout<<"r:"<<r<<" l:"<<l<<" mid:"<<mid<<endl<<endl;
}
ll len=l-i;//这里使用最左边的数，意思是最大的符合要求的数字
sum=sum+len*(len-1)/2;//组合数C（2，len）
//cout<<"sum:"<<sum<<endl;
}
cout<<sum<<endl;//输出结果就行了
}
京公网安备 11010502036488号