传送门
解题思路:
一道比较有趣的题，解题工作主要分为两块:
①找出k(k=0表示小A先走,k=1表示小B先走,下面同理)从点i出发下一个到达的点to[k][i];
一开始偷懒用了vector(偷懒一时爽),由于vector的erase操作是o(n)的,这个预处理时间复杂度就彪到o(n2)了。这里改成set就可以将复杂度降到o(nlogn),用链表的话讲道理可以降到o(n)但是排序就要o(nlogn)毫无*用。具体操作就是二分再前后比较(简称瞎搞)。
②两个人从点i出发走2j步走各自开车所走过的路程分别表示为da[i][j][k],db[i][j][k],最终达到点表示为f[i][j][k]。da[i][j][k]表示k从i点出发走了2j步的小A要开车的路程。那么da[i][j][k]+db[i][j][k]就表示了k先手开车从点i出发走了2j步共走过的路程。预处理出第一步和第二步,(转移方程见代码)。
运用二进制拆分的思想,假设出发点为s,p表示当前到达的点,ta、tb分别表示小A和小B从s出发达到p点各自走过的路程,x表示能走得最大路程。从log(最大步数)到0遍历j,如果ta+tb+da[p][j][k]+db[p][j][k]<=x,则令ta和tb分别加上da[p][j][k]和db[p][j][k],p=f[i][j][k]。枚举所有的点进行上述操作就可得到结果。
丑陋的代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; typedef long long ll; ll da[maxn][32][2],db[maxn][32][2];map <int,int> m; int h[maxn],to[2][maxn],f[maxn][32][2];set <int> v; int main() { int n;scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&h[i]),v.insert(h[i]),m[h[i]]=i; for(int i=1;i<n;i++){ v.erase(h[i]); auto id=v.lower_bound(h[i]);auto id1=id,id2=id; if(id==v.begin()){ to[0][i]=m[(*id)]; id1++; if(id1!=v.end()) to[1][i]=m[(*id1)]; } else if(id==v.end()){ id1--; if(id!=v.begin()) to[0][i]=m[(*id1)]; if(id1!=v.begin()) id1--,to[1][i]=m[(*id1)]; } else{ id1--; int t1=abs(h[i]-(*id)),t2=abs(h[i]-(*id1)); if(t1>t2){ to[0][i]=m[(*id1)];id2=id1;id2--; int t3=(id1!=v.begin())?abs(h[i]-(*id2)):2e9; if(t1>=t3) to[1][i]=m[(*id2)]; else if(t1<t3) to[1][i]=m[(*id)]; } else if(t1<t2){ to[0][i]=m[(*id)];id2++; int t3=(id2!=v.end())?abs(h[i]-(*id2)):2e9; if(t2>t3) to[1][i]=m[(*id2)]; else if(t2<=t3) to[1][i]=m[(*id1)]; } else{ to[0][i]=m[(*id1)]; to[1][i]=m[(*id)]; } } } for(int i=1;i<=n;i++) f[i][0][0]=to[1][i],f[i][0][1]=to[0][i]; for(int i=1;i<=n;i++) for(int k=0;k<=1;k++) f[i][1][k]=f[f[i][0][k]][0][1-k]; for(int j=2;j<=20;j++) for(int i=1;i<=n;i++) for(int k=0;k<=1;k++) f[i][j][k]=f[f[i][j-1][k]][j-1][k]; for(int i=1;i<=n;i++) da[i][0][0]=abs(h[(to[1][i]==0)?i:to[1][i]]-h[i]), db[i][0][1]=abs(h[(to[0][i]==0)?i:to[0][i]]-h[i]); for(int i=1;i<=n;i++) for(int k=0;k<=1;k++) da[i][1][k]=da[i][0][k]+da[f[i][0][k]][0][1-k], db[i][1][k]=db[i][0][k]+db[f[i][0][k]][0][1-k]; for(int j=2;j<=20;j++) for(int i=1;i<=n;i++) for(int k=0;k<=1;k++) da[i][j][k]=da[i][j-1][k]+da[f[i][j-1][k]][j-1][k], db[i][j][k]=db[i][j-1][k]+db[f[i][j-1][k]][j-1][k]; int x;scanf("%d",&x);int ans;double mi=1e18; for(int s=1;s<n;s++){ int p=s;ll ta=0,tb=0; for(int j=20;j>=0;j--) if(ta+tb+da[p][j][0]+db[p][j][0]<=x){ ta+=da[p][j][0]; tb+=db[p][j][0]; p=f[p][j][0]; } double t;if(tb==0) t=1e18-1; else t=(double)1.0*ta/tb; if(t<mi) ans=s,mi=t; } printf("%d ",ans); int q;scanf("%d",&q); while(q--){ int s;scanf("%d%d",&s,&x); int p=s;ll ta=0,tb=0; for(int j=20;j>=0;j--) if(ta+tb+da[p][j][0]+db[p][j][0]<=x){ ta+=da[p][j][0]; tb+=db[p][j][0]; p=f[p][j][0]; } printf("%d %d ",ta,tb); } }