题目链接: 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+10;
- int n;
- pii t[maxn];
- int f[maxn];
- int srch(int x)
- {
- int l=1, r=n;
- while(l<r)
- {
- int mid=(l+r)>>1;
- if(t[mid].fi>=x) r=mid;
- else l=mid+1;
- }
- return l;
- }
- int main()
- {
- iOS::sync_with_stdio(0);
- cin.tie(0), cout.tie(0);
- cin>>n;
- for(int i=1;i<=n;i++) cin>>t[i].fi>>t[i].se;
- sort(t+1,t+n+1);
- f[0]=0;
- for(int i=1;i<=n;i++)
- {
- int j=srch(t[i].fi-t[i].se);
- f[i]=f[j-1]+i-j;
- }
- int res=n;
- for(int i=1;i<=n;i++) res=min(res,f[i]+n-i);
- cout<<res<<endl;
- }
来源: http://www.bubuko.com/infodetail-2987785.html