题目描述

难度分:$1600$

输入$n(1 \leq n \leq 10^5)$，表示有$n$座激光塔。

然后输入$n$行，每行两个数$p[i]$$(0 \leq p[i] \leq 10^6)$和$k[i]$$(1 \leq k[i] \leq 10^6)$，表示第$i$座激光塔的位置和威力。保证所有激光塔的位置互不相同。

游戏规则：

• 按照$pos[i]$从大到小依次激活激光塔，当一座激光塔被激活时，它会摧毁它左侧所有满足$p[i]-p[j] \leq k[i]$的激光塔 $j$。被摧毁的激光塔无法被激活。

在游戏开始前，你可以在最右边的激光塔的右侧，再添加一座激光塔，位置和威力由你决定。

你希望被摧毁的激光塔的数量尽量少。输出这个最小值。

输入样例$1$

4
1 9
3 1
6 1
7 4

输出样例$1$

1

输入样例$2$

7
1 1
2 1
3 1
4 1
5 1
6 1
7 1

输出样例$2$

3

算法

动态规划

这个题看了好一阵才看明白，已经逐渐开始习惯$CF$的阅读理解风格。把所有的激光塔按照位置从小到大排序，按位置从大到小启动激光塔。$i$启动时，对于$j \lt i$且$pos[i]-pos[j]$在$i$威力范围内的所有$j$塔就会被干掉。也就是说在$i$保留，且$j$是左边离$i$最远能被干掉的塔的情况下，会干掉$i-j-1$个塔，下一次启动的塔就只能从$j-1$开始。

状态定义

$f[i]$表示在塔$i$保留的情况下，$[1,i]$范围内可以保留多少个塔。

状态转移

二分找到$i$左边能被干掉的最远塔$j$，状态转移方程即为$f[i]=1+f[j-1]$。

前后缀分解

而游戏开始之前，允许在最右边再添加一个塔，也就是说允许你干掉一个后缀$[i+1,n]$。一旦你干掉后缀的$n-i$个塔，游戏就从塔$i$开始启动，此时摧毁的塔数量就为$i-f[i]+n-i=n-f[i]$，枚举$i$维护最小值即可。

复杂度分析

时间复杂度

需要先将所有塔按照位置$pos$排序，时间复杂度为$O(nlog_2n)$。排序完成后遍历$i \in [1,n]$，从左往右进行动态规划计算$f[i]$，单词转移需要进行二分查找，时间复杂度为$O(log_2n)$。因此，算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间瓶颈在于DP数组，它是线性规模的，因此算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int n, f[N];

struct Node {
    int a, b;
    bool operator<(const Node other) const {
        return a < other.a;
    }
} node[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        f[i] = 0;
        scanf("%d%d", &node[i].a, &node[i].b);
    }
    sort(node + 1, node + n + 1);
    f[1] = 1;
    for(int i = 2; i <= n; i++) {
        int l = 1, r = i;
        while(l < r) {
            int mid = l + r >> 1;
            if(node[i].a - node[mid].a <= node[i].b) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        f[i] = 1 + f[r - 1];
    }
    int ans = n - f[n];
    for(int i = n; i >= 1; i--) {
        ans = min(ans, n - f[i]);
    }
    printf("%d\n", ans);
    return 0;
}