题解 | #ZJ19 抓捕孔连顺#(枚举+二分查找)

解题思路

1.遍历数组,依次枚举第一名特工的位置i,使用二分查找找出第三名特工的最远位置pos,则第二第三名特工的位置可在[i+1:pos]区间任意选择,累加所有选择即可,注意防止整形溢出;

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, d;
    cin >> n;
    cin >> d;
    vector<int> v(n);
    int A = 99997867, ans = 0;
    for(int i = 0; i < n; i++){ 
        int val;
        cin >> val;
        v[i] = val;
    }
    for(int i = 0; i < n - 2; i++){ //依次枚举第一名特工的位置
        int pos = upper_bound(v.begin(), v.end(), v[i] + d) - v.begin(); //大于目标值的第一个位置
        long long len = pos - i - 1; //第二及第三名特工在[i+1:pos-1]区间任选取两个位置即可
        ans = (ans + len * (len - 1) / 2 % A) % A;
    }
    cout << ans;
    return 0;
}