题意：
长度为n米的井，青蛙在井底。对于井而言，每米都有两个属性，a i , b i。a i表示在第i米时，可以向上跳[ 0 , a i ]区间里的任意米。b i表示跳到i米要下滑b i米。
问最少跳几次能够跳出井，输出每次跳后到达地方的位置坐标(下滑前)
n < = 3 e 5
思路：
从n开始进行b f s，每次将跳到并下滑后的点入队，维护到达这个点的最小步数。
优化就是维护之前能够到达的最高位置（也就是数值最小的位置）m i n n，枚举当前点能够到达的点，如果发现当前点跳出去到达的点大于等于m i n n，就跳出循环。用当前点能够达到的最高位置更新m i n n.
输出路径的话，由于是输出未下滑的点，我代码里写的入队是下滑后的点，所以又开了个a n s数组映射了一下。
具体看代码吧。
时间复杂度O ( 能 过 )
代码：
// Problem: D. Frog Traveler // Contest: Codeforces - Codeforces Round #751 (Div. 2) // URL: https://codeforces.com/contest/1602/problem/D // Memory Limit: 512 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn = 3e5 + 10; int a[maxn],b[maxn],n,pre[maxn],dis[maxn],ans[maxn]; int mii; int bfs(){ queue<int>q; mii=n; memset(pre,-1,sizeof pre); memset(dis,0x3f,sizeof dis); memset(ans,0,sizeof ans); q.push(n); dis[n]=0; while(!q.empty()){ int t=q.front();q.pop(); if(t==0) return dis[t];//跳出井了 for(int x=a[t];x>0;x--){ int now=t-x,tmp=0;//now表示跳了后的点 if(now>=mii) break;//优化 if(now>0) tmp=now,now=now+b[t-x];//维护下滑后的点 else now=0; //这里tmp为跳了后的点，now是下滑后的点 if(dis[now]>dis[t]+1){//判断下滑后的点的步数关系 dis[now]=dis[t]+1; pre[now]=t;//记录前驱 ans[now]=tmp;//记下滑前的点 q.push(now); } } mii=min(mii,t-a[t]);//更新最高位置 } return -1; } int main() { int _=1; while(_--){ n=read; rep(i,1,n) a[i]=read; rep(i,1,n) b[i]=read; printf("%d\n",bfs()); stack<int>stk; //打印路径 倒序输出 int x=0; while(pre[x]!=-1){ stk.push(x); x=pre[x]; } while(!stk.empty()){ int now=stk.top(); printf("%d ",ans[now]); // cout<<stk.top()<<" "; stk.pop(); } puts(""); } return 0; }
