牛客练习赛16 F 选值

Description:

给定n个数，从中选出三个数，使得最大的那个减最小的那个的值小于等于d，问有多少种选法。

Input:

第一行两个整数n，d(1≤n≤100,000，1≤d≤1000,000,000)；
第二行n个整数满足abs(ai)≤1,000,000,000。数据保证a单调递增。

Output:

输出一个整数表示满足条件的选法。

Sample Input:

4 3
1 2 3 4

Sample Output:

4

Sample Input:

4 2
-3 -2 -1 0

Sample Output:

2

Sample Input:

5 19
1 10 20 30 50

Sample Output:

1

题目连接

题目让找三个数最大差值 $\le d$≤d 的取法数，升序排序后枚举每一个数字做三个数的最后一个数(最大的那个数)，然后找出第一个 $\ge (枚举数-d)$≥(枚举数−d) 的数，从这个数开始到枚举数的前一个数任选两数皆可满足要求，用组合数公式计算即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;

ll n, d;
ll a[maxn];
ll sum;

int main() {
    //fropen("in.txt", "r", stdin);
    scanf("%lld %lld", &n, &d);
    sum = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    for (ll i = 1; i <= n; ++i) {
        int pos = lower_bound(a + 1, a + i, a[i] - d) - a;
        if (i - pos > 1) {
            sum += (i - pos) * (i - pos - 1) / 2;
        }
    }
    printf("%lld", sum);
    return 0;
}