题目描述
难度分:$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;
}