题目链接
有一条无限长的数轴，上面有 nn 个坑，第 ii 个坑的位置为 x_ixi。你将要在数轴上再放置 nn 个球，第 ii 个将要放到的位置为 y_iyi。每当有一个球被放上去之后，它就会滚落到离它最近的一个坑里并填上那个坑。如果有两个坑都离它最近，那么它会落到左边的里面。
现在 xuanxuan001 可以决定 nn 个球的放置顺序，为了节省时间，xuanxuan001 希望球的滚动距离总和尽量短，但他太菜了，所以需要你来帮他求出最短总距离并构造一个对应方案。
分析
首先，通过题面给的几组样例，我们可以发现，为了使总距离最小，第一个球一定和第一个坑配对，第二个球一定和第二个坑配对。。。最后一个球和最后一个坑配对。否则，总距离可能变长。我们用 $P_ {i}^{}$ 表示与 i 配对的坑。
其次，我们发现在放一个球 $i$ 之前，他的附近可能有比 $P_{i}^{}$ 更近的坑，那么这些更近的坑所配对的球一定要先于 i 放，由此我们想到拓扑排序。一条从i连向j的边表示，只有先放i才能放j，那么跑一遍拓扑排序即可。
但是，建边的最坏复杂度为 $n_{}^{2}$，因此我们需要用线段树优化建边。具体过程见代码，也可以去看P5025 [SNOI2017]炸弹
#include<bits/stdc++.h> using namespace std; #define int long long const int N=3e6+55; int b[N],k[N],n,len; struct node{ int l,r,in; }t[N]; struct edge{ int to,nex; }e[N<<2]; int cnt,head[N],dis[N],pos[N],in[N],ans[N],tot; void adda(int u,int v){ //cout<<"adda: "<<u<<" "<<v<<endl; e[++cnt].to=v;e[cnt].nex=head[u];head[u]=cnt;t[v].in+=1; } void build(int u,int L,int R){ //cout<<u<<" "<<L<<" "<<R<<endl; t[u].l=L,t[u].r=R; if(L==R){ pos[L]=u; return; } int M=(L+R)>>1; build(u<<1,L,M);build(u<<1|1,M+1,R); adda(u<<1,u);adda(u<<1|1,u); } void change(int u,int l,int r,int now){ //cout<<u<<endl; int L=t[u].l,R=t[u].r; if(L>=l&&R<=r){ adda(u,now);return; } if(L>r||R<l) return; int M=(L+R)>>1; change(u<<1,l,r,now);change(u<<1|1,l,r,now); } bool cmp(node a,node b){ return a.in<b.in; } queue<int>q; signed main(){ freopen("nameless.in","r",stdin); freopen("nameless.out","w",stdout); cin>>n; for(int i=1;i<=n;i++) scanf("%lld",&k[i]); for(int i=1;i<=n;i++){ scanf("%lld",&b[i]); dis[i]=abs(b[i]-k[i]); len+=dis[i]; } sort(k+1,k+1+n);sort(b+1,b+1+n); build(1,1,n); for(int i=1;i<=n;i++){ int mn=b[i]-dis[i],mx=b[i]+dis[i]; int r=lower_bound(k+1,k+1+n,mx)-k-1; int l=upper_bound(k+1,k+1+n,mn)-k-1; if(k[l]<mn) l++; if(k[r]>=mx) r--; if(l==i) l++; if(r==i) r--; if(l>r) continue; change(1,l,r,pos[i]); } for(int i=1;i<=n;i++){ if(t[pos[i]].in) continue; q.push(pos[i]); ans[++tot]=i; } while(!q.empty()){ int x=q.front();q.pop(); for(int i=head[x];i;i=e[i].nex){ int v=e[i].to; t[v].in--; if(!t[v].in){ q.push(v); if(t[v].l==t[v].r) ans[++tot]=t[v].l; } } } cout<<len<<endl; for(int i=1;i<=tot;i++){ printf("%lld ",ans[i]); } return 0; }