📝 题目大意

有一座长度为 $L$ 的桥，每块防护布长度为 $W$。已有 $N$ 块防护布铺设在桥上的某些位置（位置严格递增），每块布覆盖区间 $[a_i, a_i+W]$。求最少还需要多少块防护布，才能使得桥的每一段 $[0, L]$ 都被覆盖。

💡 解题思路

1. 题目分析：$N \le 10^5$，$L, W \le 10^{18}$，需要 $O(N)$ 或 $O(N \log N)$ 的解法。已有的 $N$ 块布的位置 $a_i$ 是严格递增的，且 $0 \le a_i \le L-W$。问题本质是扫描已覆盖的区间，找出所有未被覆盖的"空隙"。

2. 算法推导：

   • 将桥的右端点 $L$ 视作一个虚拟的"已铺布位置"（a.push_back(L)），这样可以将"最后一个空隙"（即最后一块布到桥尾之间的部分）统一处理。
   • 从左到右扫描，依次检查相邻两块布之间的空隙：
     • 第 $i-1$ 块布覆盖 $[a_{i-1}, a_{i-1}+W]$，第 $i$ 块布覆盖 $[a_i, a_i+W]$。
     • 若 $a_{i-1}+W \ge a_i$，说明两块布覆盖范围有重叠或恰好相接，中间没有空隙。
     • 若 $a_{i-1}+W < a_i$，说明存在空隙 $[a_{i-1}+W, a_i)$，空隙长度为 $a_i - a_{i-1} - W$。
     • 填补该空隙需要的最少布数为 $\lceil \frac{a_i - a_{i-1} - W}{W} \rceil$，等价于整数除法 $\frac{a_i - a_{i-1} - 1}{W}$（推导：$\lceil \frac{X}{W} \rceil = \frac{X+W-1}{W}$，代入 $X = a_i - a_{i-1} - W$ 即得）。
   • 起点到第一块布之间的空隙单独处理：需要 $\lceil \frac{a_0}{W} \rceil = \frac{a_0 + W - 1}{W}$ 块布来覆盖 $[0, a_0)$。
   • 累加所有空隙所需的布数即为答案。

3. 边界与细节：

   • $a_0 = 0$：第一块布从桥头开始，公式 $\frac{a_0+W-1}{W}$ 结果为 $0$，无需额外布。
   • 最后一块布已覆盖桥尾：当 $a_{N-1}+W \ge L$ 时，a.push_back(L) 后条件 a[N-1]+W < a[N] 不成立，不会额外计数。
   • 数据范围：$L, W \le 10^{18}$，必须使用 long long（C++ 中 int64_t）。标准代码中通过 #define int long long 统一处理。
   • 整数除法：C++ 中正整数除法自动向下取整，公式 $\frac{a_i - a_{i-1} - 1}{W}$ 恰好等价于所需的上取整结果。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$，仅需一次线性扫描。
• 空间复杂度：$O(N)$，存储 $N$ 个位置（使用 vector）。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
#define int long long  // 数据范围可达 1e18，统一使用 64 位整数
void solve(){
    int n, l, w;
    cin >> n >> l >> w;
    vector<int> a(n);
    for(int& i : a) cin >> i;
    a.push_back(l);  // 将桥尾 L 作为虚拟位置，统一处理最后一个空隙

    // 计算从起点 0 到第一块布之前所需的布数：ceil(a[0] / w)
    int ans = (a[0] + w - 1) / w;

    // 扫描相邻两块布，累加空隙所需的布数
    for(int i = 1; i <= n; i++){
        if(a[i-1] + w < a[i])  // 存在空隙
            ans += (a[i] - a[i-1] - 1) / w;  // ceil((a[i] - a[i-1] - w) / w)
    }
    cout << ans << '\n';
}
int32_t main(){
    int t = 1;
    while(t--) solve();
    return 0;
}