题解 | #万万没想到之抓捕孔连顺#
万万没想到之抓捕孔连顺
http://www.nowcoder.com/questionTerminal/c0803540c94848baac03096745b55b9b
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int buildnum=in.nextInt();
int farmax=in.nextInt();
int[] point=new int[buildnum];
long cont=0;
final int MOD = 99997867;
for(int i=0;i<buildnum;i++)point[i]=in.nextInt();
int b=2;
for(int a=0;a<buildnum-2;a++){
for(;b<buildnum-1&&point[b+1]-point[a]<=farmax;b++);
if(b>a+1)
cont=(cont+(long)(b-a)*(b-a-1)/2)%MOD;
}
System.out.print(cont);
}
这题目有个坑，就是数字会大到int存不下会丢失，不用累加公式会超时，用了会丢失，所以要把累加公式的数值先转为long的形式 给的数组已经是按照顺序排好了，不用再冒泡排一遍了 那么假定第一个人从一开始，只要看最后一个人能跑最远的位置就行 然后中间有多少个建筑就有多少种可能，累加起来就好，1+2+3+4这样 比如第一个人在0，第三个最远跑到3，中间有12俩个，那就有0 1 2， 0 1 3， 0 2 3三个，就是1+2
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int buildnum=in.nextInt();
int farmax=in.nextInt();
int[] point=new int[buildnum];
long cont=0;
final int MOD = 99997867;
for(int i=0;i<buildnum;i++)point[i]=in.nextInt();
int b=2;
for(int a=0;a<buildnum-2;a++){
for(;b<buildnum-1&&point[b+1]-point[a]<=farmax;b++);
if(b>a+1)
cont=(cont+(long)(b-a)*(b-a-1)/2)%MOD;
}
System.out.print(cont);
}
}
这题目有个坑，就是数字会大到int存不下会丢失，不用累加公式会超时，用了会丢失，所以要把累加公式的数值先转为long的形式 给的数组已经是按照顺序排好了，不用再冒泡排一遍了 那么假定第一个人从一开始，只要看最后一个人能跑最远的位置就行 然后中间有多少个建筑就有多少种可能，累加起来就好，1+2+3+4这样 比如第一个人在0，第三个最远跑到3，中间有12俩个，那就有0 1 2， 0 1 3， 0 2 3三个，就是1+2
