题目描述

https://www.nowcoder.com/practice/c0803540c94848baac03096745b55b9b

题解

滑动窗口 [i, j) 使得时间复杂度为 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
using namespace std;

enum {MOD = 99997867};  // 枚举定义宏

int main() {
    int n, d;
    cin >> n >> d;
    vector<int> position_build(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> position_build[i];
    }
    long long res = 0;
    for (int i = 0, j = 1; i + 2 < n; i++) {
        // 先确定第一个特工的位置 i，在之后的符合条件的建筑中找出两个建筑，数学组合问题
        // int j = i + 1;   // j 在里面定义导致每次都要从 i 开始加，没必要且 O(n^2) 会超时
        // 再确定最后一个特工的最远位置 j - 1
        while (j < n && position_build[j] - position_build[i] <= d) j++;
        // 在 x 个建筑中任意找两个不同的建筑
        long long x = j - 1 - i;
        if (x > 1) {
            res += (x * (x - 1) / 2) % MOD;
            res %= MOD;
        }
    }
    cout << res << endl;
    return 0;
}