本文主要是介绍开车旅行[巧妙的倍增][set]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
对于找第一第二近,用set+lower_bound,预处理出nxt_A nxt_B 表示A,B下一步走到哪里
然后倍增 , st_A[i][j] 表示从i往后2^j步A走了多少 B同理
nxt[i][j] 表示往后走2^j步的位置
类似lca那样预处理就好了
//一直RE但对拍一小时后的伪AC代码
#include<bits/stdc++.h>
#define N 500005
#define inf 0x3fffffff
#define LL long long
using namespace std;
LL n,x0,m;
LL a[N],h[N];
set<LL> S;
LL nxt_A[N] , nxt_B[N] , H_A[N] , H_B[N];
LL nxt[N][20] , st_A[N][20] , st_B[N][20];
LL read(){LL cnt=0,f=1;char ch=0;while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt*f;
}
void getab(LL x,LL pos,LL &ans1,LL &ans2){for(LL i=18;i>=0;i--){if(st_A[pos][i] + st_B[pos][i] <= x && nxt[pos][i]){ans1 += st_A[pos][i];ans2 += st_B[pos][i];x -= (st_A[pos][i] + st_B[pos][i]);pos = nxt[pos][i]; }}if(nxt_A[pos] && st_A[pos][0] <= x) ans1 += st_A[pos][0];
}
int main(){n=read();for(LL i=1;i<=n;i++) a[i]=read(),h[a[i]]=i;S.insert(inf) , S.insert(-inf);S.insert(a[n]) , S.insert(a[n-1]);nxt_B[n-1] = n; for(LL i=n-2;i>=1;i--){LL nxt = *S.lower_bound(a[i]);LL pre = *--S.lower_bound(a[i]);set<LL>::iterator it;it = S.lower_bound(nxt); if(*it!=inf) ++it;LL nxt_nxt = *it;it = S.lower_bound(pre); if(*it!=-inf) --it;LL pre_pre = *it;if(nxt_nxt-a[i] < a[i]-pre) nxt_A[i] = h[nxt_nxt] , nxt_B[i] = h[nxt];else if(a[i]-pre_pre <= nxt-a[i]) nxt_A[i] = h[pre_pre] , nxt_B[i] = h[pre]; else if(nxt-a[i] < a[i]-pre) nxt_A[i] = h[pre] , nxt_B[i] = h[nxt];else nxt_A[i] = h[nxt] , nxt_B[i] = h[pre];S.insert(a[i]);}for(LL i=1;i<n;i++) nxt[i][0] = nxt_B[nxt_A[i]];for(LL i=1;i<=n;i++){if(nxt_A[i]) st_A[i][0] = H_A[i] = abs(a[nxt_A[i]] - a[i]);if(nxt_B[i]) H_B[i] = abs(a[nxt_B[i]] - a[i]);if(nxt[i][0]) st_B[i][0] = abs(a[nxt[i][0]] - a[nxt_A[i]]);} for(LL i=1;i<=18;i++)for(LL j=1;j<=n;j++){nxt[j][i] = nxt[nxt[j][i-1]][i-1];st_A[j][i] = st_A[j][i-1] + st_A[nxt[j][i-1]][i-1];st_B[j][i] = st_B[j][i-1] + st_B[nxt[j][i-1]][i-1];}x0=read();LL u1=1,u2=0,H=0;LL ans=1;for(LL i=1;i<=n;i++){LL f1=0,f2=0;getab(x0,i,f1,f2);if(!f2) continue;if(f2*u1 > f1*u2 || (f2*u1 == f1*u2 && a[i]>H)) u1=f1 , u2=f2 , H=a[i] , ans=i;}printf("%lld\n",ans);m=read();while(m--){LL s=read(),x=read();LL f1=0,f2=0;getab(x,s,f1,f2);printf("%lld %lld\n",f1,f2);}return 0;
}
这篇关于开车旅行[巧妙的倍增][set]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
