网站开发软件教程,大学生网站设计论文范文,网站店铺分布图怎么做,同步网站内容怎么做正题
题目链接:https://www.luogu.com.cn/problem/CF1066F 题目大意
平面上有nnn个点#xff0c;每个点在max(x,y)max(x,y)max(x,y)层#xff0c;走第kkk层的点之前一定要先走前面层的点#xff0c;求走完所有点的最短路。 解题思路
对于每一层来说#xff0c;我们可以将…正题
题目链接:https://www.luogu.com.cn/problem/CF1066F 题目大意
平面上有nnn个点每个点在max(x,y)max(x,y)max(x,y)层走第kkk层的点之前一定要先走前面层的点求走完所有点的最短路。 解题思路
对于每一层来说我们可以将其看成一条直线那么我们走某一层一定是先走到最边上的点再走到另一边最边上的点因为如果这两个点也是必走的如果没有走到这个点不行如果走到了这个点那么这边的所有点一定已经走到过。
所以排序来做即可 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
#define ll long long
using namespace std;
const ll N2e610;
ll n,cnt,x[N],y[N],z[N],b[N*2];
ll mx[N],mn[N],f[N],dmin,dmax;
vectorll 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 i1;in;i){scanf(%lld%lld,x[i],y[i]);b[cnt]x[i];b[cnt]y[i];}sort(b1,b1cnt);cntunique(b1,b1cnt)-b-1;for(ll i1;in;i){x[i]lower_bound(b1,b1cnt,x[i])-b;y[i]lower_bound(b1,b1cnt,y[i])-b;ll kmax(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 last0;for(ll i1;icnt;i){if(q[i].empty())continue; sort(q[i].begin(),q[i].end());for(ll j0;jq[i].size();j){ll xx,yy;if(q[i][j]0)yyb[i],xxq[i][j]b[i];else xxb[i],yyb[i]-q[i][j];f[j]min(dmaxget_dis(xx,yy,b[x[mx[last]]],b[y[mx[last]]]),dminget_dis(xx,yy,b[x[mn[last]]],b[y[mn[last]]]));}dmaxdmin1e18;for(ll j0;jq[i].size();j){dmaxmin(dmax,f[j]q[i][j]z[mx[i]]-2*z[mn[i]]);dminmin(dmin,f[j]z[mx[i]]*2-q[i][j]-z[mn[i]]);}lasti;}printf(%lld,min(dmax,dmin));
}
