题解 | #万万没想到之抓捕孔连顺#
万万没想到之抓捕孔连顺
https://www.nowcoder.com/practice/c0803540c94848baac03096745b55b9b
代码思路：
双指针 + 组合数
定义j指针，遍历a[j] - a[i] <= d，就是当前第一个在i位置得到最远能到的j位置,再从i + 1 到 j中选两个位置
//双指针算法
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, mod = 99997867;
ll a[N];
ll n, d;
int main(){
cin >> n >> d;
ll ans = 0;
for(int i = 0; i < n; i ++) cin >> a[i];
for(int i = 0, j = 0; i < n; i ++){
while(j + 1 < n && a[j + 1] - a[i] <= d) j ++;
ans += ll((ll)(j - i) * (ll)(j - i - 1) / 2) % mod;
ans %= mod;
}
cout << ans << endl;
return 0;
}
查看4道真题和解析