Codeforces 892 B. Wrath （递推）（思维）
发布时间
阅读量：
阅读量
题意
每个人都有一个长度为 li 的武器，相邻的两个人之间距离为 1 ，同一时间所有人使用武器攻击左边的人，问最后存活下来的人数。
显然，最右侧的人一定是可以存活下来的。
我们维护一个 cntcnt 代表右侧延伸到当前位置的武器长度，
若 cnt>0说明当前位置在别人的攻击范围内，否则 ans+1 。
更新 cnt为 max(cnt−1,ai)看对于 ii 来说是否可以攻击到更远的位置。
时间复杂度 O(n)O。
ps：个人认为也可以用差分写，有空再补一下
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1.5e6+5;
const int MAXM = 1.5e6+5;
typedef long long ll;
int a[MAXN];
int main(){
int n ;
cin >> n;
for(int i = 1; i <= n ; i++) cin >> a[i];
int ans = a[n]; int len = 1;
for(int i = n - 1 ; i >= 1; i --){
if(ans > 0) len++;
ans --;
ans = max(ans , a[i]);
}
cout << n - len + 1 << endl;
}全部评论 (0)
还没有任何评论哟~