正題

題目鏈接:https://www.luogu.com.cn/problem/CF1066F

---

題目大意

平面上有$n$個點，每個點在$max(x,y)$層，走第$k$層的點之前一定要先走前面層的點，求走完所有點的最短路。

---

解題思路

對于每一層來說，我們可以將其看成一條直線，那么我們走某一層一定是先走到最邊上的點再走到另一邊最邊上的點，因為如果這兩個點也是必走的，如果沒有走到這個點不行，如果走到了這個點，那么這邊的所有點一定已經走到過。

所以排序來做即可

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ll long long using namespace std; const ll N=2e6+10; ll n,cnt,x[N],y[N],z[N],b[N*2]; ll mx[N],mn[N],f[N],dmin,dmax; vector<ll> q[N]; ll get_dis(ll x1,ll y1,ll x2,ll y2) {return abs(x1-x2)+abs(y1-y2);} int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++){scanf("%lld%lld",&x[i],&y[i]);b[++cnt]=x[i];b[++cnt]=y[i];}sort(b+1,b+1+cnt);cnt=unique(b+1,b+1+cnt)-b-1;for(ll i=1;i<=n;i++){x[i]=lower_bound(b+1,b+1+cnt,x[i])-b;y[i]=lower_bound(b+1,b+1+cnt,y[i])-b;ll k=max(x[i],y[i]);if(x[i]==k) q[k].push_back(z[i]=b[k]-b[y[i]]);else q[k].push_back(z[i]=b[x[i]]-b[k]);if(z[i]>z[mx[k]]||!mx[k])mx[k]=i;if(z[i]<z[mn[k]]||!mn[k])mn[k]=i;}ll last=0;for(ll i=1;i<=cnt;i++){if(q[i].empty())continue; sort(q[i].begin(),q[i].end());for(ll j=0;j<q[i].size();j++){ll xx,yy;if(q[i][j]<0)yy=b[i],xx=q[i][j]+b[i];else xx=b[i],yy=b[i]-q[i][j];f[j]=min(dmax+get_dis(xx,yy,b[x[mx[last]]],b[y[mx[last]]]),dmin+get_dis(xx,yy,b[x[mn[last]]],b[y[mn[last]]]));}dmax=dmin=1e18;for(ll j=0;j<q[i].size();j++){dmax=min(dmax,f[j]+q[i][j]+z[mx[i]]-2*z[mn[i]]);dmin=min(dmin,f[j]+z[mx[i]]*2-q[i][j]-z[mn[i]]);}last=i;}printf("%lld",min(dmax,dmin)); }

總結

以上是生活随笔為你收集整理的CF1066F-Yet another 2D Walking【贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。