一个好玩的编程小游戏——埋伏行动

大家好，欢迎来到IT知识分享网。

题目：

我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工。

1. 我们在字节跳动大街的N个建筑中选定3个埋伏地点。

2. 为了相互照应，我们决定相距最远的两名特工间的距离不超过D。

我特喵是个天才！经过精密的计算，我们从x中可行的埋伏方案中选出一种，这个方案万无一失，颤抖吧，孔连顺！

……

万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在人群中逃出了字节跳动大街。只怪他的伪装太成功了。

请听题：给定N（可选作为埋伏点的建筑物数）、D（距离最远的两名特工的最大值）以及可选建筑物的坐标，计算在这次行动中，共有多少种埋伏选择。

注意：

1.两个特工不能埋伏在同一地点

2.三个特工是等价的：即同样的位置组合（A、B、C）只算一种方案，特工之间互换位置不算。

输入描述：

第一行包含空格分隔的两个数字N和D（1<=N<=1000000, 1<=D<=N）。

第二行包含N个建筑物的位置，每个位置用一个整数表示，从小到大排列（将字节跳动大街看做一个数组）

输出描述：

一个数字，表示不同埋伏方案的数量。结果可能溢出，请对999……（博主：照片没拍到，忘了是什么了）取模。

分析：

最大距离D确定后，可埋伏区间必为某段连续区间。从左到右扫描整个数组，记录每个位置埋伏一个人使，其余两人在右边埋伏共有多少种可能，最终全部相加得到结果。
代码：

a = input().split()
b = input().split()
n, d = int(a[0]), int(b[0])
alist = [int(x) for x in b]
#n, d = 7, 3
#alist = [1, 5, 6, 7, 8, 12, 13]
 
ambush_kinds = []          # 记录第一个人埋伏在当前位置时，其他人的埋伏的种类
start = 0        # 指向第一个埋伏的人
end = 0        # 指向最后一个人最远埋伏距离
 
# 定义组合函数C_n^k
def c(n, k):
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator *= n-i
        denominator *= k-i
    return numerator / denominator
 
while start < n-2:                      # 终止条件：三个人埋伏在最后三个位置
    # 找到当前start对应的end的最远位置
    while end < n and alist[end] - alist[start] <= d:
        end += 1
    ambush_range = end - start          # 计算三人埋伏的范围
    if ambush_range < 3:                # 如果此范围太小不够三人埋伏，计数为0
        ambush_kinds.append(0)
    else:                               # 一人埋伏在start位置时，取余两人的埋伏种类
        ambush_kinds.append(c(ambush_range-1, 2))
    start += 1                          # 计算下一个start
print(sum(ambush_kinds))
#print(ambush_kinds)