CF252C_Points on Line

keywords: 双指针

这道题目的题意，是显然的。阅读理解没啥困难，就是找三个点，最大距离不能超过d。然后还友好的告诉你给你的数据是严格递增的，这显然具有单调性，然后看数据范围，好家伙二分走你，或者用尺取法。

写一下题解，记录一个细节，主要是没理解为什么那个公式是 ��2

首先给出正式代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int a[N], n, d;
ll ret;

int main()
{
    cin >> n >> d;
    for (int i = 0; i < n; i++) cin >> a[i];

    int i, j = 0;
    for (i = 0; i + 2 < n; i++){
        while (j < n && a[j] - a[i] <= d) j++;
        if (j - i <= 1) continue;  //i j连在一起无法构成三个点

        ll k = ((j - 1) - i + 1) - 1; //a[i]固定，在其余的点里面Ck2, 任选两个就o了
        ret += k * (k-1) / 2; //Cn2 公式
    }

    cout << ret << '\n';

    return 0;
}

//网上题解并没有准确的说明k是怎么来的，让我数学蒟蒻思考了很久，因为我自己的做法是下面这样的

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

ll n, d, ret;
ll a[N];

int main()
{
    cin >> n >> d;
    for (int i = 0; i < n; i++) cin >> a[i];

    int i, j;
    for (i = 0; i < n-2; i++){
        j = i;
        while (j < n && a[j] - a[i] <= d) j++;

        ll k = j - 1 - i + 1 - 2; 
        ret += k * (k + 1) / 2;  //我这种思考方式，依次固定左端点，枚举右端点，中间点有几种选择，等差求和公式
    }

    cout << ret << '\n';

    return 0;
}

总结：进一步熟悉two pointers，当然二分也是一样的

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int a[N], n, d;
ll ret;

int main()
{
    cin >> n >> d;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i + 2 < n; i++){
        int j = upper_bound(a + i, a + n, a[i] + d) - a;
        if (j - i <= 1) continue;

        ll k = ((j - 1) - i + 1) - 1; //a[i]固定，在其余的点里面Ck2, 任选两个就o了
        ret += k * (k-1) / 2; //Cn2 公式
    }

    cout << ret << '\n';

    return 0;
}