题解 CF1214F 【Employment】

首先，最优的方案必然满足： > 按照$a,b$升序排列，指定$a_1$对应$b_k$，那么$a_i$必然对应$b_{(k+i-1)\% n + 1}$ 换句话说，只要确定一个断环的位置，那么最优的方案就唯一确定了，在断环后的序列中，每一个人都去寻找自己最近的一个目标。 可以用微扰法简单证明。 > 若存在两个相邻元素$x,y$，设其目标为$b_x,b_y$，但是$p_{b_x} > p_{b_y}$，那么显然交换两个元素的目标，答案会更优。 通过这个贪心，问题就转化为： > 对$a,b$排序后，设$d\in[0,n)$为增量 ， 求$\min\limits_{d=0}^{n-1} \{\sum\limits_{i=1}^{n} dist(a_i,b_{i+d})\}$ 于是我们可以用$O(n^2)$来求解。 为了更快速的解决问题，我们需要对上述算法优化。 假设 $j = i + d$，那么区间长度为$d = j - i$。 - $a_i \leq b_j$ , $b_j - a_i \leq a_i - b_j + m$ , 贡献为$(-a_i) + (b_j)$ - $a_i \leq b_j$ , $b_j - a_i > a_i - b_j + m$ , 贡献为$(-a_i+ m) + (b_j)$ - $a_i > b_j$ , $a_i - b_j \leq b_j - a_i + m$ , 贡献为$(a_i) - (b_j)$ - $a_i > b_j$ , $a_i - b_j > b_j - a_i + m$ , 贡献为$(-a_i) + (b_j +m)$ 对于每一个增量$d$的答案是$f_d$，那么显然这些$f_d$都是分别由$a_i$和$b_i$来贡献的。 我们可以使用$O(n)$的复杂度确定一个$a_i$，然后将符合条件的$b_j$来归成四种可能中的一种，分别用$a_i$对应的贡献，去更新$f_{j-i}$的值。 具体来说，若指定的$a_i$让$b_j$在区间$j \in [l,r]$中满足： - $2a_i \leq 2b_j \leq 2a_i+m$ , 我们就用$-a_i$的贡献去更新$d \in [l-i,r-i]$ - $2a_i + m+ 1\leq 2b_j $ , 我们就用$a_i + m$的贡献去更新$d \in [l-i,r-i]$ - $2a_i - m\leq 2b_j\leq 2a_i - 1 $ , 我们就用$a_i$的贡献去更新$d \in [l-i,r-i]$ - $ 2b_j\leq 2a_i - m-1 $ , 我们就用$-a_i$的贡献去更新$d \in [l-i,r-i]$ 注意到，上述的分类讨论我们发现对于一个确定的$a_i$，对于$b_j$数组来说，被切分为最多$4$段，对于每一段里的$d = j - i $都使用相同的关于$a_i$的贡献来区间更新。 这显然可以使用差分来维护。 同理，如果我们使用$O(n)$的复杂度去确定一个$b_j$，那么对应位$a_i$同样会被切分成最多$4$段，每段都使用相同的关于$b_j$的贡献来更新。 本题总复杂度$O(n \ log_2 \ n )$。 ```cpp # pragma GCC optimize(3) # include<bits/stdc++.h> # define int long long using namespace std; const int N=2e5+10; int a[N],b[N],aa[N],bb[N],c[N],ans[N]; int n,m; pair<int,int>t1[N],t2[N]; inline int read() { int X=0,w=0; char c=0; while(c<'0'||c>'9') {w|=c=='-';c=getchar();} while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar(); return w?-X:X; } void update(int l,int r,int d){c[l]+=d; c[r+1]-=d;} void modify(int l,int r,int d) { if (l>r) return; l=((l+n)%n+n)%n; r=((r+n)%n+n)%n; if (l>r) update(l,n-1,d),update(0,r,d); else update(l,r,d); } signed main() { m=read();n=read(); for (int i=1;i<=n;i++) t1[i]=make_pair(read(),i); for (int i=1;i<=n;i++) t2[i]=make_pair(read(),i); sort(t1+1,t1+1+n); sort(t2+1,t2+1+n); for (int i=1;i<=n;i++) { a[i]=t1[i].first; aa[i]=a[i]<<1; b[i]=t2[i].first; bb[i]=b[i]<<1; } for (int i=1;i<=n;i++) { int l=1,r=upper_bound(bb+1,bb+1+n,aa[i]-m-1)-bb-1; modify(l-i,r-i,-a[i]); l=r+1; r=upper_bound(bb+1,bb+1+n,aa[i]-1)-bb-1; modify(l-i,r-i,a[i]); l=r+1; r=upper_bound(bb+1,bb+1+n,aa[i]+m)-bb-1; modify(l-i,r-i,-a[i]); l=r+1; r=n; modify(l-i,r-i,a[i]+m); } for (int i=1;i<=n;i++) { int l=1,r=upper_bound(aa+1,aa+1+n,bb[i]-m-1)-aa-1; modify(i-r,i-l,-b[i]); l=r+1; r=upper_bound(aa+1,aa+1+n,bb[i])-aa-1; modify(i-r,i-l,b[i]); l=r+1; r=upper_bound(aa+1,aa+1+n,bb[i]+m)-aa-1; modify(i-r,i-l,-b[i]); l=r+1; r=n; modify(i-r,i-l,b[i]+m); } int pos=0; for (int i=1;i<n;i++) c[i]+=c[i-1],pos=(c[i]<c[pos])?i:pos; printf("%lld\n",c[pos]); for (int i=1,j=pos+1;i<=n;i++,j=(j==n)?1:j+1) ans[t1[i].second]=t2[j].second; for (int i=1;i<=n;i++) printf("%lld ",ans[i]); puts(""); return 0; } ```