P10132 [USACO24JAN] Cannonball B

jiangjiangQwQ · 2024-02-06 17:51:39 · 题解

思路

数据范围不大，但是要考虑触发一个跳板之后弹到另一个跳板又恰好跳回原来的位置，这样会死循环，解决方法有两种，一种就是限制跳的次数，一种就是记录到达这个跳板时的信息，下次到达判断是否重复跳过。对于两个方向跳跃，可以设置一个方向变量，取值为 -1 或 1，用当前位置加上跳的距离乘上这个方向变量就可以跳到下一个位置。遇到跳板时将这个变量取反，这个有点类似于快读里的判断负数，剩下的放代码注释更好理解了。

代码

#include<iostream>
#include<map>
using namespace std;
const int N=2e5+5;
int n,s,q[N],v[N];
bool vis[N];
int sum,cnt;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>q[i]>>v[i];
        if(q[i]==1) cnt++;
    }
    int nl=1,f=1,tot=0;//nf表示当前能量
   //f是方向变量,tot是我的跳跃次数
    while(s<=n&&s>=1&&sum<cnt&&tot<=n*3){
        ++tot;
        if(q[s]==1&&nl>=v[s]){//遇到目标
            if(vis[s]==0) sum++;//之前没有摧毁
            vis[s]=1;//标记已摧毁
        }
        else if(q[s]==0){//遇到跳板
            nl+=v[s];//能量值变化
            f=-f;//方向取反
            vis[s]=1;//标记访问
        }
        s+=nl*f;//移动位置
    }
    cout<<sum;//输出摧毁的目标数
    return 0;
}