训练反应力 | Decade

训练反应力【算法赛】

问题描述

小蓝正在努力成为一名航空员，这需要他锻炼出足够的反应力。

他来到一台用来训练反应力的机器前，训练的规则如下：小蓝可以选择在 N 个时间节点进行攻击。在某个时间节点 X 攻击机器后，机器将在 X + D 节点反击小蓝。此时，小蓝需要躲避，如果被机器击中，任务将失败。

小蓝无法在同一时间节点同时进行攻击和躲避。他想知道，在确保任务成功的前提下，自己最多能攻击机器多少次。

输入格式

第一行包含两个整数 N, D (1<=N<=1e5,1<=D<=1e9)，分别表示时间节点的数量和机器反击的延迟。

第二行包含 N 个整数 A_i (A₁ < A₂ < ⋯ < A_N ≤ 1e9)，表示时间节点的具体值。

输出格式

输出一个整数，表示小蓝在确保任务成功的前提下，最多能攻击机器的次数。

样例输入

1 2	5 2 1 3 4 6 8

样例输出

思路

很明显的贪心，类似于活动选择问题：即当前时刻如果能攻击，则攻击。

需要一个严谨的贪心证明，这个证明与活动选择问题思路大致相同，但要分两种情况：

假设最终的最优攻击的时间点序列：x₁, x₂, ⋯, x_n，其中不存在x_i + D = x_j, ∀i, j ≤ n。

反证法：假设x₀并不在最优序列中（原始序列第一个值记作x₀）

x₁ + D < x₂，那么由于x₀ < x₁，有x₀ + D < x₂，此时可以将答案序列中的x₁替换成x₀，即此时x₀在最优序列中。
x₁ + D > x₂，此时还要分两种情况：
1. x₀ + D = x₂，那此时说明选了x₀后就不能再选x₂，但由于x₂ > x1，所以x₀ + D = x₂ > x₁，所以此时可以删去最优序列中的x₂，换成x₀。因为x₀不会和x₁冲突，更不可能和x₃, x₄⋯冲突。此时x₀在最优序列中。
2. x₀ + D ≠ x₂，那此时说明选了x₀和x₂不会冲突，直接将x₁替换为x₀，序列中元素数量不变，此时x₀在最优序列中

综上，作为原始序列的最小值x₀，总是存在于最优序列中，于是可以遍历原始序列，依次加入当前状态下可以加入的最小值。

代码

void solve() {
    cin >> n >> m;
    int ans = 0;
    unordered_set<int> ban;
    for (int i = 1, cur = 0;i <= n;i++) {
        cin >> cur;
        if (!ban.count(cur)) {
            ++ans;
            ban.insert(cur + m);
        }
    }
    pl(ans);
}

复杂度

时间：O(n)
空间：O(n)