-
预处理出小A和小B在每个城市下次到达的城市，即距离每个点的最近点和次近点
-
本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近
- \(sort\) 将海拔 \(h\) 排序，并用 \(b\) 数组记录出排序后每个城市的位置，b[原编号]=排序后的位置
-
编号较小的城市在编号较大的城市的西边，且计划一直向东行驶
-
即一直向初始编号大的城市行驶，可以从\(1\rightarrow n\)遍历初始编号，走过一个城市删一个，这样可以保证在考虑范围内的城市全部都是初始编号比当前城市大的
-
要维护与当前城市距离最近的两座城市，以及支持删除操作，用双向链表维护
-
\(eg:\)
\(h\)数组：\(\enclose{circle}{1}\) \(\enclose{circle}{2}\) \(\enclose{circle}{3}\) \(\enclose{circle}{4}\)
\(\qquad\quad\,\large5\) \(\,\,\,\large1\) \(\,\,\large7\) \(\,\,\,\large4\)
\(b\)数组：\(b[2]=1 \quad b[4]=2 \quad b[1]=3 \quad b[3]=4\)
\(\enclose{circle}{2}\) \(\enclose{circle}{4}\) \(\enclose{circle}{1}\) \(\enclose{circle}{3}\)
\(\,\,\large1\) \(\,\,\large4\) \(\,\,\large5\) \(\,\,\large7\)
\[\enclose{circle}{1} \Longleftrightarrow \enclose{circle}{2} \Longleftrightarrow\enclose{circle}{3} \Longleftrightarrow \enclose{circle}{4} \]当\(i=1\)时，\(u=pre[b[i]]=2,\ v=nxt[b[i]]=4\)
\[\enclose{circle}{1} \Longleftrightarrow \enclose{circle}{2} \Longleftrightarrow \enclose{circle}{4} \]当\(i=2\)时，\(u=pre[b[i]]=\emptyset,\ v=nxt[b[i]]=2\)
\[\ \enclose{circle}{2} \Longleftrightarrow \enclose{circle}{4} \]当\(i=3\)时，\(u=pre[b[i]]=2,\ v=nxt[b[i]]=\emptyset\)
\[\enclose{circle}{2} \] -
for(int i=1;i<=n;i++){cin>>a[i].h;a[i].id=i;nxt[i]=i+1;pre[i]=i-1;}nxt[0]=nxt[n]=0;sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++)b[a[i].id]=i;//A数组，B数组：下次到达城市的序号，AW，BW：行驶的路程for(int i=1;i<=n;i++){int u=pre[b[i]],v=nxt[b[i]];if(!u&&!v) continue;if(v&&(!u||abs(a[u].h-a[b[i]].h)>abs(a[v].h-a[b[i]].h))){B[i]=a[v].id;BW[i]=abs(a[v].h-a[b[i]].h);}else if(u&&(!v||abs(a[v].h-a[b[i]].h)>abs(a[u].h-a[b[i]].h))){B[i]=a[u].id;BW[i]=abs(a[u].h-a[b[i]].h);}else if(u&&v){if(abs(a[v].h-a[b[i]].h)<abs(a[u].h-a[b[i]].h)){B[i]=a[v].id;BW[i]=abs(a[v].h-a[b[i]].h);}else{B[i]=a[u].id;BW[i]=abs(a[u].h-a[b[i]].h);}}if(u) nxt[u]=v;if(v) pre[v]=u;}for(int i=1;i<=n;i++){nxt[i]=i+1;pre[i]=i-1;}pre[0]=nxt[n]=nxt[0]=0;for(int i=1;i<=n;i++){int u=pre[b[i]],v=nxt[b[i]];if(!u&&!v) continue;if((!u&&nxt[v])||(u&&nxt[v]&&abs(a[u].h-a[b[i]].h)>abs(a[b[i]].h-a[nxt[v]].h))){A[i]=a[nxt[v]].id;AW[i]=abs(a[b[i]].h-a[nxt[v]].h);}else if((!v&&pre[u])||(v&&pre[u]&&abs(a[v].h-a[b[i]].h)>=abs(a[pre[u]].h-a[b[i]].h))){A[i]=a[pre[u]].id;AW[i]=abs(a[pre[u]].h-a[b[i]].h);}else if(u&&v){//距离相等时选前驱对应题目中"距离相同则选海拔较低"的规则（前驱海拔更低）if(abs(a[v].h-a[b[i]].h)<abs(a[u].h-a[b[i]].h)){A[i]=a[u].id;AW[i]=abs(a[u].h-a[b[i]].h);}else{A[i]=a[v].id;AW[i]=abs(a[v].h-a[b[i]].h);}}if(u) nxt[u]=v;if(v) pre[v]=u;}注意判定当前元素的前驱和后继不存在的情况
-
-
-
倍增优化移动过程
-
\(s[i][j]\) 表示从\(i\)号节点小\(A\)和小\(B\)各走\(2^j\)步到达的节点
\(SW[i][j]\) 表示从\(i\)号节点小\(A\)和小\(B\)各走\(2^j\)步的权值
\(SA[i][j]\) 表示从\(i\)号节点小\(A\)走\(2^j\)步的权值
\(SB[i][j]\) 表示从\(i\)号节点小\(B\)走\(2^j\)步的权值
-
for(int i=1;i<=n;i++){if(A[i]&&B[A[i]]){s[i][0]=B[A[i]];SW[i][0]=min(INF,AW[i]+BW[A[i]]);SB[i][0]=min(INF,BW[A[i]]);SA[i][0]=min(INF,AW[i]);}}for(int j=1;j<20;j++){for(int i=1;i<=n;i++){if(s[i][j-1]&&s[s[i][j-1]][j-1]){s[i][j]=s[s[i][j-1]][j-1];SW[i][j]=min(INF,SW[i][j-1]+SW[s[i][j-1]][j-1]);SB[i][j]=min(INF,SB[i][j-1]+SB[s[i][j-1]][j-1]);SA[i][j]=min(INF,SA[i][j-1]+SA[s[i][j-1]][j-1]);}}}
-
-
\(question\)
-
\(question1:\) 枚举出发城市 \(s\)，从大往小尝试行驶的组数以二为底数的幂指数，满足条件就行驶，累加总路程与小\(A\)和小\(B\)行驶的路程，到达极限后，再尝试一下小\(A\)能不能再走，最后用交叉相乘比较大小
- \(ans1\)记录小\(A\)的路程，\(ans2\)记录小\(B\)的路程，初始化\(ans1=10^9+5,\, ans2=0\) (\(x_i\leq 10^9\)，所以\(ans1\)的初始值必须比\(10^9\)大，设为极值)
-
\(question2:\) 从大往小尝试行驶的组数以二为底数的幂指数，满足条件就行驶，累加小\(A\)和小\(B\)行驶的路程，到达极限后，再尝试一下小\(A\)能不能再走
-
cin>>x;int ans1=INF+1,ans2=0,t=0;//t记录编号 for(int i=1;i<=n;i++){int sA=0,sB=0,S=0;int u=i;for(int j=19;j>=0;j--){if(s[u][j]){if((ll)S+SW[u][j]<=x){S+=SW[u][j];sA+=SA[u][j];sB+=SB[u][j];u=s[u][j];}}}if(A[u]&&S+AW[u]<=x) sA+=AW[u];if((ll)ans1*sB>(ll)sA*ans2){ans1=sA;ans2=sB;t=i;}}cout<<t<<'\n';cin>>m;while(m--){cin>>st>>x;int S=0,sA=0,sB=0;for(int j=19;j>=0;j--){if(s[st][j]){if((ll)S+SW[st][j]<=x){S+=SW[st][j];sA+=SA[st][j];sB+=SB[st][j];st=s[st][j];}}}if(A[st]&&S+AW[st]<=x) sA+=AW[st];cout<<sA<<" "<<sB<<'\n';}
-
