CF1214F Employment 题解

Codeforces
Luogu

Description.

环上有 \(n\) 个源点 \(n\) 个汇点。
匹配它们使得距离和最短,输出方案。

Solution.

首先路径肯定不会相交。

然后我们破环成链。
把 \(b_i-m\),\(b_i\),\(b_i+m\) 当成 \(b_i\)。
然后设差值是 \(x\),则贡献是下式

\[\begin{aligned} &b_{i+n}=b_{i}+m\\ rs&=\sum_{i=1}^n|a_i-b_{i+x}|\\ &=\sum_{i=1}^nxs_i(a_i-b_{i+x})\\ &=\sum_{i=1}^nxs_ia_i-\sum_{i=1}^nxs_ib_{i+x}\\ &=\sum_{i=1}^nA_{x,i}a_i-\sum_{i=1}^nB_{x,i+x}b_{i+x}\\ &=\sum_{i=1}^nA_{x,i}a_i-\sum_{i=1+x}^{n+x}B_{x,i}b_{i} \end{aligned} \]

\(xs_i\) 表示若 \(a_i\ge b_{i+x}\) 则它为 \(1\) 否则为 \(-1\)。
随着 \(x\) 的增大,\(xs_i\) 肯定会从 \(1\) 变成 \(-1\),总共有 \(O(n)\) 个变化,可以维护。
主要是后面的那个 \(b_{i+x}\) 怎么维护
考虑 \(b_{i+x}\) 的贡献,在 \(i+x\) 不变的情况下我们发现 \(xs_i\) 单调不降。
\(A_{x,i}\) 表示 \(a_i\ge b_{i+x}\),\(B_{x,i}\) 表示 \(a_{i-x}\ge b_{i}\)。
则 \(A_{x}\) 在 \(x\) 递增时会从 \(1\) 变向 \(-1\),\(B_{x}\) 在 \(x\) 递增时会从 \(1\) 变成 \(-1\)。
可以预处理出 \(A_{?,i}\) 和 \(B_{?,i}\) 什么时候改变,然后就做完了。

Coding.

点击查看代码
//是啊,你就是那只鬼了,所以被你碰到以后,就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
	x=0;char c=getchar(),f=0;
	for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
	for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=600005;int m,n,ot[N];
struct bit
{
	int n;ll T[N];inline void init(int x) {n=x;}
	inline void add(int x,ll w) {for(;x<=n;x+=x&(-x)) T[x]+=w;}
	inline ll qry(int x) {ll r=0;for(;x;x-=x&(-x)) r+=T[x];return r;}
	inline ll qry(int l,int r) {return qry(r)-qry(l-1);}
}A,B;vector<int>va[N],vb[N];
struct ${int id;ll vl;char operator<($ b) const {return vl<b.vl;}}a[N],b[N];
//#define debug
int main()
{
	read(m,n);for(int i=1;i<=n;i++) read(a[i].vl),a[i].id=i,a[i].vl+=m;
	for(int i=1;i<=n;i++) read(b[i].vl),b[i].id=i,b[i+n]=b[i+n+n]=b[i];
	for(int i=1;i<=n;i++) b[i+n].vl=b[i].vl+m,b[i+n+n].vl=b[i+n].vl+m;
	sort(a+1,a+n+1),sort(b+1,b+n*3+1),A.init(n),B.init(n*3);
#ifdef debug
	for(int i=1;i<=n;i++) printf("%lld%c",a[i].vl,i==n?'\n':' ');
	for(int i=1;i<=n*3;i++) printf("%lld%c",b[i].vl,i==n*3?'\n':' ');
#endif
	for(int i=n+1;i<=n*3;i++) a[i].vl=2e9+5;
	for(int i=1;i<=n;i++) if(a[i].vl>=b[i].vl)
	{
		int wh=upper_bound(b+1,b+n*3+1,a[i])-b;
		va[wh-i].push_back(i);
#ifdef debug
		printf("%d : %d\n",wh-i,i);
#endif
	}
	for(int i=1;i<=n*3;i++) if(a[i].vl>=b[i].vl)
	{
		int wh=lower_bound(a,a+n+2,b[i])-a-1;
		vb[i-wh].push_back(i);
#ifdef debug
		printf("%d : %d\n",i-wh,i);
#endif
	}
	for(int i=1;i<=n;i++) A.add(i,a[i].vl>=b[i].vl?a[i].vl:-a[i].vl);
	for(int i=1;i<=n*3;i++) B.add(i,a[i].vl>=b[i].vl?b[i].vl:-b[i].vl);
	ll rs=A.qry(1,n)-B.qry(1,n);int wh=0;
#ifdef debug
	printf("qwq %d : %lld\n",0,rs);
#endif
	for(int x=1;x<n+n;x++)
	{
		for(auto i:va[x]) A.add(i,-2*a[i].vl);
		for(auto i:vb[x]) B.add(i,-2*b[i].vl);
		ll nw=A.qry(1,n)-B.qry(x+1,x+n);if(rs>nw) rs=nw,wh=x;
#ifdef debug
		printf("qwq %d : %lld\n",x,nw);
		for(int i=1;i<=n;i++) printf("%lld%c",A.qry(i,i),i==n?'\n':' ');
		for(int i=1;i<=n*3;i++) printf("%lld%c",B.qry(i,i),i==n*3?'\n':' ');
#endif
	}
	printf("%lld\n",rs);
	for(int i=1;i<=n;i++) ot[a[i].id]=b[i+wh].id;
	for(int i=1;i<=n;i++) printf("%d%c",ot[i],i==n?'\n':' ');
	return 0;
}
上一篇:windows下lib和dll区别


下一篇:牛表