题目链接：https://codeforces.com/problemset/problem/607/A
题意：
有 $n$ 个塔排成一行，第 $i$ 个激光塔的位置为 $a_i$，伤害范围是 $b_i$，激活第 $i$ 个塔后，所有在这个塔左侧且距离小于等于 $b_i$ 的塔都会被摧毁，但该塔本身不会被摧毁。
现在会从右向左依次激活每个塔，如果一个塔被摧毁则无法被激活。
现在要在这 $n$ 个激光塔的右边再放一个塔，该塔的位置和威力是任意的。现在从这个新加入的塔开始从右到左依次激活每个塔，求最小摧毁的塔数。
题解：
$f[i]$ 表示前 $i$ 个塔，最少会摧毁多少座。假设 $j$ 表示位置在区间 $[a_i-b_i,a_i]$ 内最左侧塔的编号。
那么，$f[i] = f[j-1] + cnt(a_i-b_i,a_i)$，其中 $cnt(a_i-b_i,a_i)$ 表示启动第 $i$ 个塔，则区间 $[a_i-b_i,a_i]$ 之中有多少个塔被摧毁，很显然 $cnt(a_i-b_i,a_i) = (i-1) - j +1 = i - j$。
所以关键就是找到区间 $[a_i-b_i,a_i]$ 中第一个塔的编号是多少，这个可以用二分就可以了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
const int maxn=1e5+;
int n;
pii t[maxn];
int f[maxn];
int srch(int x)
{
int l=, r=n;
while(l<r)
{
int mid=(l+r)>>;
if(t[mid].fi>=x) r=mid;
else l=mid+;
}
return l;
}
int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n;
for(int i=;i<=n;i++) cin>>t[i].fi>>t[i].se;
sort(t+,t+n+); f[]=;
for(int i=;i<=n;i++)
{
int j=srch(t[i].fi-t[i].se);
f[i]=f[j-]+i-j;
} int res=n;
for(int i=;i<=n;i++) res=min(res,f[i]+n-i);
cout<<res<<endl;
}