正题

题目链接: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【贪心】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。