字节跳动笔试真题第三弹，2021第一天从算法题开始吧！

点击上方蓝字，关注并星标，和我一起学技术。

大家好，今天是2021年的第一天，让我们鼓足干劲大干一场。今天我们选择的依然是字节跳动2019年的笔试题，题目来源于牛客网。

这道题难度同样不是很大，但是非常考验基础，基础稍稍不够扎实的同学很有可能写出了算法，但是依然会陷入各种问题当中无法AC。我个人觉得差不多是LeetCode Medium水平的难度，但是需要大家有点耐心，开动脑筋反复思考。

题目链接：https://www.nowcoder.com/question/next?pid=16516564&qid=362293&tid=40247384

好了，我们不多说废话，直接来看题吧。

题意

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

1. 我们在字节跳动大街的N个建筑中选定3个埋伏地点。
2. 为了相互照应，我们决定相距最远的两名特工间的距离不超过D。

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

……

万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！

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

注意：

1. 两个特工不能埋伏在同一地点
2. 三个特工是等价的：即同样的位置组合(A, B, C) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用

输入描述:

第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)

第二行包含N个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）

输出描述:

一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模

输入例子1:

4 3
1 2 3 4

输出例子1:

4

例子说明1:

可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)

输入例子2:

5 19
1 10 20 30 50

输出例子2:

1

例子说明2:

可选方案 (1, 10, 20)

题解

首先我们来理一下题目当中出现的几个点，我们要算的是特工埋伏的方法数。特工埋伏需要固定3个特工，并且要求特工之间的距离小于D。

题目当中还说特工之间是等价的，如果大家敏感的话，这其实是一道排列组合问题，准确的说是一道组合问题。这和n球里任意取3个出来有多少种组合本质上是一样的，如果大家还记得组合公式的话套一下就可以了：

这里的k固定了是3，我们代入进去可以简化为：

，所以现在唯一的问题就是n不知道。我们可以知道n是可以通过D来进行计算的，至于怎么计算我们先放一放，先来对问题进行一个建模。

首先，由于题目当中说的是特工分布在一条大街上，我们可以把大街看成是横坐标轴，每一个特工就是坐标轴上的一个点。由于题目当中限定了3个特工之间的距离不超过D，其实也就是最左侧和最右侧的距离小于D。我们可以想象有一个长度为D的线段在这个坐标轴上滑动，窗口内的特工数量就是n。

由于特工的位置是固定的，所以这个n是很好算的。假如我们用一个数组sum来存储从0开始到当前位置一共包含的特工数，那么区间[x, x+D]范围内的特工数量其实就等于sum[x+D]-sum[x]。这里我们可以通过差分数组来搞定，也可以使用树状数组，我这里用了树状数组，其实没有必要，因为不涉及更新操作。

所以接下来我们要做的就是把这个窗口从最左侧往右滑动就可以了，每次窗口内特工变化的时候，我们计算一下构成的组合数累加在一起就可以了。进一步我们可以想到，其实我们只需要关心窗口的左边缘，我们把窗口的左边缘和特工重叠，这样能够使得窗口内的特工数量尽可能多。

比如[1, 2, 3, 4]这个样例，显然当窗口的左边缘和1重叠的时候，能够把4也覆盖了，否则就会遗漏一些情况。很多人想到这里就去写代码了，但是这里藏了一个trick，当我们的窗口移动的时候，实际上会出现有一些组合重复的情况。

比如说窗口长度是4，当前窗口内的特工是[1, 2, 3, 4]，其中有一种组合是(2, 3, 4)。当我们窗口左侧边缘移动到2的时候，窗口内的特工是[2, 3, 4, 5]，这里同样可以构成组合(2, 3, 4)，这就构成了重复，我们需要去掉这一种方案。去的方法也很简单，我们每次移动窗口的时候都记录下移动之前的窗口右边缘的位置。当我们移动之后，我们当前左侧边缘和上次右侧边缘中的特工是重复的，我们需要去掉相关情况。

比如说，我们移动之前是[1, 5, 6, 7]，移动之后是[5, 6, 7, 8, 10, 12]。当前的左侧边缘是5，上次的右侧边缘是7，[5, 7]这个区间内的组合数就是重复的情况， 我们需要去掉。另外我们还需要注意一下边界的事情，由于我们计算组合数需要用到三方的计算，而n最大是1e6，三次方之后就是1e18的范围，显然使用int是扛不住的，必须要用long long， long long的范围是2e18，基本上注意这几点就可以AC了。

最后，我们来看代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
#define pii pair<int, int>
using namespace std;
const int N=1000050;
const long long Mod=99997867;
int x, y;

int arr[N];

// 树状数组
int lowbit(int x) {
    return x & (-x);
}

void update(int x, int y) {
    for (int i = x; i < N; i += lowbit(i)) {
        arr[i] += y;
    }
}

int query(int x) {
    int ret = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        ret += arr[i];
    }
    return ret;
}

long long cal(long long x) {
    return x * (x-1) * (x-2) / (long long) 6;
}

int main() {
    int n, d;
    scanf("%d%d", &n, &d);
    vector<int> positions;
    rep(i, 0, n) {
        int u;
        scanf("%d", &u);
        u += 1;
        positions.push_back(u);
        update(u, 1);
    }
    long long ret = 0;

    int last = 0;
    for (int i = 0; i < positions.size(); i++) {
        int u = positions[i];
        
        long long num = query(u+d) - query(u-1);
        if (num < 3) continue;

        long long cur = cal(num);
        // 去掉重复的可能性
        if (last > u) {
            long long cnum = query(last) - query(u-1);
            cur -= cal(cnum);
        }
        ret = ((ret + cur) % Mod + Mod) % Mod;
        last = u + d;
    }
    printf("%lld\n", ret);
    return 0;
}

代码里有一个细节，我们在对最终结果进行取模的时候，不是直接% Mod，而是用了一个比较复杂的方式：ret = ((ret + cur) % Mod + Mod) % Mod;。这是因为我们直接取模在一些情况下可能会得到负数，会影响我们的结果，所以需要通过这种方式来确保得到的结果一定是正数。

今天的文章就到这里，衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话，请来一个三连支持吧~（点赞、在看、转发）