官方题解

题目大意

给定 $n$ 个同学在数轴上的位置 $x_i$，每辆车最多载 $2$ 人，且两人之间距离满足 $|x_i-x_j|\le D$ 才能拼车。求最少需要多少辆车使所有同学都能回家。

题解思路

要让车辆数最少，就要让“拼车的对数”尽量多，因为每拼成一对就比两人各自打车少用一辆车。

把所有位置 $x_i$ 排序为 $p_1\le p_2\le \dots \le p_n$。在有序序列上从左到右扫描：

• 如果 $p_{i+1}-p_i\le D$，就把这两位同学配成一对，然后跳过这两人；
• 否则 $p_i$ 无法与任何更右侧的人拼车（更右只会更远），只能单独一辆车。

这是最大化不相交配对数的典型贪心：能配就立刻配相邻元素。设配对数为 pairs，答案为

$$\text{cars}=n-\text{pairs}.$$

复杂度：排序 $O(n\log n)$，扫描 $O(n)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long D;
    cin >> n >> D;

    vector<long long> x(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    sort(x.begin(), x.end());

    int pairs = 0;
    int i = 0;
    while (i + 1 < n) {
        if (x[i + 1] - x[i] <= D) {
            pairs++;
            i += 2;
        } else {
            i += 1;
        }
    }

    cout << (n - pairs) << "\n";
    return 0;
}