題目連接

題意

題目已經(jīng)說的hin明確了。

題解

我們要求出從每個(gè)點(diǎn)出發(fā)，小A要走的城市和小B要走的城市。

我們把ii以后的所有點(diǎn)的海拔加入到setset，然后拿H[i]H[i]到set里面去lower_bound,找到比H[i]大的兩個(gè)地點(diǎn)和比H[i]小的兩個(gè)地點(diǎn)，并把這四個(gè)地點(diǎn)與H[i]的差值加入到新的排序數(shù)組中，排個(gè)序，找到差值最小的兩個(gè)點(diǎn)，分別就是小B要選的目的地和小A要選的目的地。
在這里注意一點(diǎn)，就是當(dāng)差值最小的兩個(gè)值相等的時(shí)候，小B走的是海拔較低的那個(gè)點(diǎn)，涉及到第二關(guān)鍵字的問題，我們可以用一個(gè)比較省事的方法，那就是給海拔低的點(diǎn)計(jì)算差值時(shí)候乘以99999999，海拔較高的點(diǎn)計(jì)算差值時(shí)候乘以100000000。

定義需要的狀態(tài)

nxt1[i]nxt1[i]代表從ii出發(fā)，小B的目的地。
nxt2[i]nxt2[i]代表從ii出發(fā)，小A的目的地。
nxt3[i][j]nxt3[i][j]代表從ii出發(fā)，(小A走完、小B走完)2j2j輪，所達(dá)到的目的
地。

DP1[i][j]DP1[i][j]代表從i出發(fā)，(小A走完、小B走完)2j2j輪，小B所經(jīng)過的距離。

DP2[i][j]DP2[i][j]代表從i出發(fā)，(小A走完、小B走完)2j2j輪，小A所經(jīng)過的距離。

nxt3,DP1,DP2可以用類似于處理ST表的方法求出來。

函數(shù)解釋

一輪代表小A走一次+小B走一次。
getdp(int &S,int len,ll &ans1,ll &ans2)
從S出發(fā)，走len輪，返回ans1為小B走過的路程，返回ans2為小A走過的路程，并且把S改變?yōu)閘en輪以后到達(dá)的點(diǎn)。
getmx(int S,ll X)
從S出發(fā)，總路程不能超過X，返回最大能走幾輪。

回答詢問

給出SiSi和XiXi，用二分的方法求出從Si出發(fā)小A和小B最長能走的長度。

---

代碼

// luogu-judger-enable-o2 #include <iostream> #include <cstdio> #include <algorithm> #include <set> using namespace std; typedef long long ll; typedef pair<ll,int> pll; set<pll>::iterator it; const int maxn = 500007; int nxt1[maxn],nxt2[maxn],nxt3[maxn][30]; int N,LOG,X0,M; ll H[maxn],H2[maxn],H1[maxn],DP2[maxn][30],DP1[maxn][30]; pll tmpsort[7]; void getdp(int &S,int len,ll &ans1,ll &ans2){int cnt = 0;while(len){if(len & 1){ans1 += DP1[S][cnt];ans2 += DP2[S][cnt];S = nxt3[S][cnt];}len >>= 1;cnt++;if(!S) break;}return ; } int getmx(int S,ll X){int l = 0,mid,r = N+1;while(r - l > 1){mid = (l+r)/2;int nS = S;ll ans1 = 0,ans2 = 0;getdp(nS,mid,ans1,ans2);if(ans1+ans2 > X || !nS)r = mid;else l = mid;}return l; } int main(){set<pll> st;cin>>N;int tmp = 1;while(tmp <= N/3)LOG++,tmp <<= 1;for(int i = 1;i <= N;++i){scanf("%lld",&H[i]);st.insert(make_pair(H[i],i));}for(int i = 1;i < N;++i){int ct = 0;st.erase(make_pair(H[i],i));it = st.lower_bound(make_pair(H[i],i));if(it != st.end()){tmpsort[ct++] = make_pair(abs(H[i]-(*it).first)*100000000,(*it).second); ++it;}if(it != st.end()){tmpsort[ct++] = make_pair(abs(H[i]-(*it).first)*100000000,(*it).second); } it = st.lower_bound(make_pair(H[i],i));if(it != st.begin()) {--it;tmpsort[ct++] = make_pair(abs(H[i]-(*it).first)*99999999,(*it).second); if(it != st.begin()){--it;tmpsort[ct++] = make_pair(abs(H[i]-(*it).first)*99999999,(*it).second); }}sort(tmpsort,tmpsort+ct);if(ct > 0)nxt1[i] = tmpsort[0].second;if(ct > 1)nxt2[i] = tmpsort[1].second;}for(int i = 1;i < N;++i)nxt3[i][0] = nxt1[nxt2[i]];for(int i =1;i <= N;++i){if(nxt1[i])H1[i] = abs(H[nxt1[i]] - H[i]);if(nxt2[i]){H2[i] = abs(H[nxt2[i]] - H[i]);DP2[i][0] = abs(H[nxt2[i]] - H[i]);}if(nxt1[nxt2[i]])DP1[i][0] = abs(H[nxt1[nxt2[i]]] - H[nxt2[i]]);}for(int j = 1;j <= LOG;++j){for(int i = 1;i <= N;++i){nxt3[i][j] = nxt3[nxt3[i][j-1]][j-1];DP1[i][j] = DP1[i][j-1] + DP1[nxt3[i][j-1]][j-1];DP2[i][j] = DP2[i][j-1] + DP2[nxt3[i][j-1]][j-1];}}int mf1 = 0,mf2 = 1,mh = 0;int ans1 = 1;cin>>X0>>M;for(int i = 1;i <= N;++i){ll f1 = 0,f2 = 0;int nS = i;int mxl = getmx(i,X0);getdp(nS,mxl,f1,f2);if(nxt2[nS] && H2[nS]+f1+f2 <= X0)f2 += H2[nS];if(!f2) continue;if(mf1*f2 < f1*mf2){mf1 = f1;mf2 = f2;ans1 = i;mh = H[i];}else if(mf1*f2 == mf2*f1 && H[i] > mh){mf1 = f1;mf2 = f2;ans1 = i;mh = H[i];}}cout<<ans1<<endl;for(int i = 0;i < M;++i){int Si,nSi;ll Xi;scanf("%d %lld",&Si,&Xi);nSi = Si;int mxl = getmx(Si,Xi);ll f1 = 0,f2 = 0;getdp(nSi,mxl,f1,f2);if(nxt2[nSi] && H2[nSi]+f1+f2 <= Xi)f2 += H2[nSi];printf("%lld %lld\n",f2,f1);}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的P1081 开车旅行 倍增 洛谷的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。