第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)
第二行包含N个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）
一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模
4 3 1 2 3 4
4
可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)
5 19 1 10 20 30 50
1
可选方案 (1, 10, 20)
2 100 1 102
0
无可选方案
#include<iostream>usingnamespacestd;longlongC(longlongn){return(n - 1) * n / 2;}longlongSelect(longlongarr[], longlongd, longlongn){if(n < 3)return0;longlongi = 0, j = 2, count = 0;while(j < n){if(j - i < 2){j++;}elseif(arr[j] - arr[i] > d){i++;}elseif(arr[j] - arr[i] <= d){count += C(j - i);j++;}}returncount;}intmain(){longlongn, d, i, j = 0;cin >> n;cin >> d;longlong*arr = (longlong*)calloc(sizeof(longlong), (size_t)n);i = n;while(i){cin >> arr[j++];i--;}cout << Select(arr, d, n) % 99997867 ;free(arr);return0;}
#include <iostream>
#include <vector>
using namespace std;
long long C(long long n){
return (n-1) * n / 2;
}
int main()
{
long long n, d, count = 0;
cin>> n>> d;
vector<long long> v(n);
for (int i = 0, j = 0; i < n; i++) {
cin>> v[i];
while (i >= 2 && (v[i] - v[j]) > d) {
j++;
}
count += C(i - j);
}
cout << count % 99997867;
return 0;
}
时间复杂度O(N)
n, dist = map(int, input().split())
nums = list(map(int, input().split()))
res = 0
left = 0
right = 2
while left < n-2:
while right < n and nums[right] - nums[left] <= dist:
right += 1
if right - 1 - left >= 2:
num = right - left - 1
res += num * (num - 1) // 2
left += 1
print(res % 99997867)
import java.util.*;
public class Main {
private int mod = 99997867;
private void sln() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(), D = sc.nextInt();
long cnt = 0;
if (N <= 2) {
System.out.println(-1);
return;
}
int[] locs = new int[N];
for (int i = 0; i < N; i++) {
locs[i] = sc.nextInt();
}
sc.close();
int left = 0, right = 2;
while (right < N) {
if (locs[right] - locs[left] > D) left++;
else if (right - left < 2) right++;
else {
cnt += calC(right - left);
right++;
}
}
cnt %= mod;
System.out.println(cnt);
}
private long calC(long num) {
return num * (num - 1) / 2;
}
public static void main(String[] args) {
new Main().sln();
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int D = sc.nextInt();
int[] dist = new int[N];
for (int i = 0; i < N; i++) {
dist[i] = sc.nextInt();
}
long i = new Solution().totalProgram(dist, D);
System.out.println(i);
}
}
class Solution {
private final int mod = 99997867;
private long ans = 0;
public long totalProgram(int[] dist, int D) {
for (int i = 0,j = 0;i<dist.length;i++){
while (i >= 2 && (dist[i] - dist[j]) > D)
j++;
ans += computeCn(i - j);
}
return ans % mod;
}
private long computeCn(long n) {
return n * (n - 1) / 2;
}
}
computeCn一定要用long的参数和输出都要用long
//很多人说复杂度会比较高，认为内层循环需要要二叉查找降低复杂度，这个思路确实可行。
但是实际上，对于第二层以j为下标的循环，我们完全不需要每次都从j=i+2进行循环，可以单独用变量right存放上次循环的结果，下一次循环直接从j=right开始就可以了。
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int N=in.nextInt();
int D=in.nextInt();
int [] location =new int [N];
for(int i=0 ;i<N;i++){
location[i]=in.nextInt();
}
long count =0L;
int right=2;
for(int i=0;i<N-2;i++){
long temp=0L;
for(int j=right;j<N;j++) {
if(location[j]-location[i]>D) {
break;
}else {
temp=(long)(j-i);
right=j;
}
}
if(temp>=2)
count+=temp*(temp-1)/2%99997867;
}
System.out.println(count%99997867);
}
}
} 
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n,d,res=0;
cin>>n>>d;
long long a[n];
for (long long i = 0, j = 0; i < n; i++)
{
cin>>a[i];
while (i >= 2 && (a[i] - a[j]) > d)
j++;
res +=(i - j-1) * (i - j) / 2;
}
cout<<res%99997867;
return 0;
}
MOD = 99997867 def solve(n, d, nums): """ 改进算法,nums是递增的,j不用每次都重新计算,类似滑动窗口 dp[i]: 以nums[i]为最大元素的方案数 i: 遍历到的数字 j: 与i相差距离>d的最近的坐标索引 时间复杂度O(n) ac :param n: :param d: :param nums: :return: """ dp = [0] * n dp[2] = 1 if nums[2] - nums[0] <= d else 0 j = 0 for i in range(3, n): while j < i and nums[j] + d < nums[i]: j += 1 c = i - j dp[i] += c * (c - 1) // 2 if c >= 3 else 0 dp[i] %= MOD return sum(dp) % MOD def solve2(n, d, nums): """ 暴力解法: dp[i] 以nums[i]为最大元素的方案数 时间复杂度0(n^2) 30% 超时 :param n: :param d: :param nums: :return: """ dp = [0] * n dp[2] = 1 if nums[2] - nums[0] <= d else 0 for i in range(3, n): c = 0 j = i - 1 while j >= 0 and nums[j] + d >= nums[i]: c += 1 j -= 1 dp[i] += c * (c - 1) // 2 if c >= 3 else 0 dp[i] %= MOD return sum(dp) % MOD N, D = list(map(int, input().split())) nums = list(map(int, input().split())) print(solve(N, D, nums))
import java.util.*;
public class Main{
public static void main (String[] args){
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int D=sc.nextInt();
int []s=new int[N];
long num=0;
for(int i=0;i<N;i++){
s[i]=sc.nextInt();
}
//注意这里的for循环中，声明了j=i+2，不知道为什么把这个声明放在for循环内部就会有超时报错。求解
for(int i=0,j=i+2;i<N-2;i++){
long p;
while(j<N&&(s[j]-s[i]<=D))
j++;
p=j-i-1;
num=num+(p*(p-1)/2);
}
System.out.println(num%99997867);
}
//注意这里的for循环中，声明了j=i+2，不知道为什么把这个声明放在for循环内部就会有超时报错。求解！！！！！！！！！！！！！！！！
整体思路就是对于每个最前面的埋伏者，我们找到符合条件的最后一个埋伏者，这样对于第一个埋伏者已经确定的情况下，我们从中间选出另外两个进行组合，最后相加即可！！
} 
import java.util.*;
public class Main{
public static int binary(int left, int right, int k, int[] a){
while(left<=right){
int mid = (right+left)/2;
if(a[mid] == k)
return mid;
else if(a[mid] < k){
left = mid + 1;
}else{
right = mid - 1;
}
}
return right;
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt(); int d = in.nextInt();
int[] a = new int[n];
for(int i=0; i<n; i++){
a[i] = in.nextInt();
}
long count=0;
for(int i=0; i<=n-3; i++){
int pos = binary(i, n-1, a[i]+d, a);
long ans = ((long)(pos-i)*(pos-i-1)/2)%99997867;
count = (count + ans)%99997867;
}
System.out.println(count);
}
}
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n, d;
n = sc.nextInt();
d = sc.nextInt();
int[] a = new int[n+1];
for (int i = 0 ; i < n; i++){
a[i] = sc.nextInt();
}
// 从左到右会超时，因为右节点有回头，每一次都需要j重置到i+1的位置。
// run_left(n, d, a);
// 改用从右到左判断，i每次向后移，j必定在当前值的基础上进行移动。即以最右边的节点作为“定点”
run_right(n, d, a);
}
public static void run_right(int n, int d, int[] a) {
Long result = 0L;
for (int i = 2, j = 0 ; i < n; i++){
while(a[i] - a[j] > d) {
// 因为即使 a[i] - a[i-1] >d, 当j==i 的时候，不满足 a[i] - a[j] > d 的条件
// 所以这里不会使 j > i
j++;
}
// 两者想乘可能会 超过 int 的返回，导致结果为负，输出的结果错误
result += ((long)(i-j)*(long)(i-j-1)/2);
}
System.out.println(result % 99997867);
}
public static void run_left(int n, int d, int[] a) {
Long result = 0L;
for (int i = 0 ; i < n-2; i++){
int j = i + 1;
while(j+1 < n && a[j+1] - a[i] <= d) {
j++;
}
result += ((j-i)*(j-i-1)/2);
}
System.out.println(result % 99997867);
}
} 
#include<iostream>
#include<vector>
using namespace std;
int main() {
int N, D;
cin >> N >> D;
vector<int> nums(N);
long long res = 0;
for (int i = 0; i < N; ++i) {
cin >> nums[i];
}
for (int i = 0; i < N - 2; ++i) {
auto p = lower_bound(nums.begin()+i+1, nums.end(), nums[i]+D);
if (p != nums.end() && *p == nums[i] + D)
++p;
long long length = p - nums.begin() - i;
if (length >= 3) {
res += (length - 1) * (length - 2) / 2;
}
}
cout << res % 99997867 << endl;
return 0;
} 
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N;
cin>>N;
int maxDist;
cin>>maxDist;
vector<int> build(N);
for(int i=0;i<N;i++) {
cin>>build[i];
}
int left=0,right=2;
long long count = 0;
while(right<N) {
while(build[right]-build[left]>maxDist) {
left++;
}
if(build[right]-build[left]<=maxDist) {
if(right-left>=2) {
long long n = right-left+1;
count += ((n-1)*(n-2))/2;
}
}
right++;
}
cout<<count%99997867<<endl;
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
