简要题意
求一个抽象函数，满足 \(∀? ∈ ℤ, ?(?) + ? = ?(2?(?) − ? + 1)\)，给定 \(n\) 个点，使得 \(\sum |f(x_i)-y_i|\) 最小，输出最小值
思路
对这个函数进行一次迭代，可以得到 \(f(x+2C)=f(x)+2C\)
有了这个结论，我们就可以只对 \(x\in[0,2C)\) 进行讨论
这时我们考虑，如果有了一个 \(a\) 和 \(f(a)\) ，我们还可以确定一个 \(b=2*f(a)-a+1\)，所以 \(a+b=2*f(a)+1\)，所以 \(a,b\) 的奇偶性不同，那现在我们就可以将 \(a,b\) 匹配的过程看作二分图匹配，匹配的代价就是 \(n\) 个点中和\(a,b\)同余的点的代价再算上一堆奇妙柿子的代价，最后跑二分图带权匹配即可
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 10005
#define CC 655
int n,C,top;
int x[N],y[N],q[N];
vector<int> num[CC];
int suan(int x){
int ans=0;
for(int i=1;i<=top;i++) ans+=abs(q[i]+x);
return ans;
}
int cal(int a,int b){
int X=a/2,Y=b/2;top=0;
for(auto id:num[a]) q[++top]=X+Y+x[id]-a-y[id];
for(auto id:num[b]) q[++top]=-X-Y+b-x[id]-C+y[id];
sort(q+1,q+1+top);
int mid=q[(top+1)/2]/C;
return min(suan(-mid*C),min(suan(-(mid+1)*C),suan(-(mid-1)*C)));
}
struct AB{
int a,b,c,v,n;
};
namespace FYL{
int k=1,head,tail,S,T;
const int inf=1e9;
int h[CC],hh[CC],dis[CC],u[CC],vis[CC],q[CC*CC],sh[CC];
AB d[CC*CC*3];
void cun(int x,int y,int z,int w){
d[++k]={x,y,z,w,h[x]},h[x]=k;
}
void link(int x,int y,int z,int w){
cun(x,y,z,w),cun(y,x,0,-w);
}
void spfa(){
memset(dis,9,sizeof(dis));
memset(u,0,sizeof(u));
q[head=tail=1]=S,dis[S]=0,u[S]=1;
while(head<=tail){
int x=q[head++];
u[x]=0;
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(!d[i].c||dis[x]+d[i].v>=dis[y]) continue;
dis[y]=dis[x]+d[i].v;
if(!u[y]) q[++tail]=y,u[y]=1;
}
}
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > qq;
void dij(){
memset(dis,9,sizeof(dis));
memset(u,0,sizeof(u));
dis[S]=0,qq.push({0,S});
while(!qq.empty()){
int x=qq.top().second;qq.pop();
if(u[x]) continue;
u[x]=1;
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(!d[i].c||dis[x]+d[i].v+sh[x]-sh[y]>=dis[y]) continue;
dis[y]=dis[x]+d[i].v+sh[x]-sh[y],qq.push({dis[y],y});
}
}
}
int dfs(int x,int f){
if(x==T) return f;
int ff=f;vis[x]=1;
for(int &i=h[x];i;i=d[i].n){
int y=d[i].b;
if(!d[i].c||dis[y]!=dis[x]+d[i].v+sh[x]-sh[y]||vis[y]) continue;
int fl=dfs(y,min(f,d[i].c));
if(fl) d[i].c-=fl,d[i^1].c+=fl,f-=fl;
if(!f) break;
}
if(ff-f) vis[x]=0;
return ff-f;
}
int dinic(){
int ans1=0,ans2=0;
memcpy(hh,h,sizeof(h));
spfa();
for(int i=0;i<=T;i++) sh[i]+=dis[i];
while(1){
memcpy(h,hh,sizeof(hh));
dij();
if(dis[T]==dis[T+1]) break;
memset(vis,0,sizeof(vis));
int fl=dfs(S,inf);
if(!fl) break;
ans1+=fl,ans2+=fl*(dis[T]+sh[T]);
for(int i=0;i<=T;i++) sh[i]+=dis[i];
}
return ans2;
}
}
signed main(){
freopen("function.in","r",stdin);
freopen("function.out","w",stdout);
scanf("%lld%lld",&n,&C);
FYL::S=2*C,FYL::T=FYL::S+1;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&x[i],&y[i]);
num[x[i]%(2*C)].push_back(i);
}
for(int i=0;i<2*C;i+=2){
for(int j=1;j<2*C;j+=2) FYL::link(i,j,1,cal(i,j));
}
for(int i=0;i<2*C;i+=2) FYL::link(FYL::S,i,1,0);
for(int i=1;i<2*C;i+=2) FYL::link(i,FYL::T,1,0);
printf("%lld\n",FYL::dinic());
return 0;
}