题目链接:https://www.nowcoder.com/acm/contest/84/F
因为题目要求最大值减去最小值的差要小于等于d,所以我们从i=2开始遍历数组,以当前的pre[i]为最大值,然后二分去查找一个最小值,然后判断两者之间的长度是否不相邻,不相邻的话用组合数求出从中选取两个数的方案数。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#define ll long long
using namespace std;
ll n,d;
ll pre[100005];
int main()
{
scanf("%lld%lld",&n,&d);
for(int i=0;i<n;i++){
scanf("%lld",&pre[i]);
}
ll sum = 0;
for(int i=2;i<n;i++){
int ans = lower_bound(pre,pre+n,pre[i] - d) - pre;
ans = i - ans;
if(ans >= 2){
sum += (ll)(ans-1)*(ll)ans/(ll)2;
}
}
printf("%lld\n",sum);
return 0;
}