T3 函数
首先存在结论 \(f(a+2C)=f(a)+2C\) 。
简单证明，设 \(b=2f(a)-a+1\) ，那么 \(f(b)=f(a)+C\) ，设 \(d=2f(b)-b+1\) ，那么 \(f(d)=f(a)+2C\) ，同时：
\[\begin{aligned} d&=2f(b)-b+1\\ &=2f(a)+2C-2f(a)+a-1+1\\ &=a+2C \end{aligned} \]根据结论可以知道，我们可以将函数 \(f(x)\) 按照 \(x\operatorname{mod} 2C\) 分组，每组可以表示为 \(a+2kC\) 的形式。
设 \(b=2f(a)-a+1\) ，那么 \(a+b=2f(a)+1\) ，考虑将 \(a, b\) 的范围限制在 \([0,2C)\) 中，设 \(a=a'+2kC, b=b'+2tC\) ，那么有 \(a'+b'+2kC+2tC=2f(a'+2kC)+1=f(a')+4kC+1\) ，那么 \(a'+b'=f(a')+2kC-2tC+1\) ，由于 \(b\) 由 \(f(a)\) 决定，因此 \(t\) 的取值任意，简化一下有： \(a'+b'=f(a')-2nC+1\) 。
容易发现 \(a', b'\) 奇偶性不同，不妨设 \(a'=2X, b'=2Y+1\) ，那么有：
\[\begin{aligned} a'+b'&=2f(a')+1-2nC\\ 2X+2Y+1&=2f(a')+1-2nC\\ 2f(a')&=2X+2Y+2nC\\ f(a')&=X+Y+nC \end{aligned} \]\[\begin{aligned} f(b')&=f(a'+2kC)+C-2tC\\ f(b')&=f(a')+C-2nC\\ f(b')&=X+Y-(n-1)C \end{aligned} \]对于 \(a'\) ，如果确定了 \(f(a')\) ，那么就唯一确定其对应的 \(b'\) 以及 \(f(b')\) ，不难发现这构成了两两配对的关系，因此考虑一对配对的 \(a', b'\) 所造成的贡献。
考虑一组点 \((x_i, y_i)\) ，如果 \(x_i\) 属于 \(a'\) 组内，设 \(x_i=2kC+a'\) ，那么：
\[\begin{aligned} |f(x_i)-y_i|&=|f(a'+2kC)-y_i|\\ &=|f(a')+2kC-y_i|\\ &=|X+Y+nC+2kC-y_i| \end{aligned} \]设 \(W_i=X+Y+2kC-y_i\) ，那么 \(|f(x_i)-y_i|=|W_i+nC|\) 。
如果 \(x_i\) 属于 \(b'\) 组内，设 \(x_i=2kC+b'\) ，那么：
\[\begin{aligned} |f(x_i)-y_i|&=|f(b'+2kC)-y_i|\\ &=|f(b')+2kC-y_i|\\ &=|X+Y-(n-1)C+2kC-y_i|\\ &=|y_i-X-Y-2kC-C+nC| \end{aligned} \]设 \(W_i=y_i-X-Y-2kC-C\) ，那么 \(|f(x_i)-y_i|=|W_i+nC|\) 。
直接二分图最大权匹配即可。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <cassert>
using namespace std;
const int max1 = 600;
const int inf = 0x3f3f3f3f;
int n, C;
vector < pair <int, int> > bin[max1 + 5];
struct Graph_Net
{
struct Node
{
int next, v, flow;
long long cost;
}edge[max1 * max1 + 5];
int head[max1 + 5], total;
int s, t;
int maxflow;
long long mincost;
long long dis[max1 + 5], h[max1 + 5];
int flow[max1 + 5], pre_point[max1 + 5], pre_edge[max1 + 5];
bool vis[max1 + 5];
struct Point
{
int x; long long d;
Point () {}
Point ( int __x, long long __d )
{ x = __x, d = __d; }
bool operator < ( const Point &A ) const
{ return d > A.d; }
};
priority_queue <Point> que;
void Clear ()
{
memset(head, 0, sizeof(int) * (C + C + 2));
total = 1;
return;
}
void Add ( int u, int v, int f, long long c )
{
edge[++total].v = v;
edge[total].flow = f;
edge[total].cost = c;
edge[total].next = head[u];
head[u] = total;
return;
}
void Add_Edge ( int u, int v, int f, long long c )
{
return Add(u, v, f, c), Add(v, u, 0, -c);
}
bool Dijikstra ()
{
while ( !que.empty() )
que.pop();
memset(dis, 0x3f, sizeof(long long) * (C + C + 2));
memset(vis, 0, sizeof(bool) * (C + C + 2));
dis[s] = 0; flow[s] = inf; pre_point[s] = pre_edge[s] = -1;
que.push(Point(s, 0));
while ( !que.empty() )
{
int x = que.top().x; que.pop();
if ( vis[x] )
continue;
vis[x] = true;
for ( int i = head[x]; i; i = edge[i].next )
{
int v = edge[i].v, f = edge[i].flow;
long long c = edge[i].cost + h[x] - h[v];
if ( f && dis[v] > dis[x] + c )
{
assert(c >= 0);
dis[v] = dis[x] + c;
flow[v] = min(flow[x], f);
pre_point[v] = x;
pre_edge[v] = i;
que.push(Point(v, dis[v]));
}
}
}
return vis[t];
}
void Update ()
{
for ( int i = 0; i < C + C + 2; i ++ )
h[i] += dis[i];
maxflow += flow[t];
mincost += h[t] * flow[t];
int x = t;
while ( x != s )
{
edge[pre_edge[x]].flow -= flow[t];
edge[pre_edge[x] ^ 1].flow += flow[t];
x = pre_point[x];
}
return;
}
void EK ()
{
memset(h, 0, sizeof(long long) * (C + C + 2));
maxflow = mincost = 0;
while ( Dijikstra() )
Update();
return;
}
}Graph;
long long Calc ( const vector <int> &val, int p )
{
long long sum = 0;
for ( auto v : val )
sum += abs(p - v);
return sum;
}
long long Connect ( int u, int v, int X, int Y )
{
vector <int> val; val.clear();
for ( auto x : bin[u] )
val.push_back(-x.second + X + Y + x.first * C * 2);
for ( auto x : bin[v] )
val.push_back(x.second - X - Y - x.first * C * 2 - C);
if ( val.empty() )
return 0LL;
sort(val.begin(), val.end());
int mid = val.size() >> 1;
mid = val[mid] / C;
return min({ Calc(val, (mid - 1) * C), Calc(val, mid * C), Calc(val, (mid + 1) * C) });
}
int main ()
{
freopen("function.in", "r", stdin);
freopen("function.out", "w", stdout);
scanf("%d%d", &n, &C);
for ( int i = 1, x, y; i <= n; i ++ )
{
scanf("%d%d", &x, &y);
bin[x % (C + C)].push_back(make_pair(x / (C + C), y));
}
Graph.Clear();
for ( int i = 0; i < C; i ++ )
for ( int j = 0; j < C; j ++ )
Graph.Add_Edge(i + i, j + j + 1, 1, Connect(i + i, j + j + 1, i, j));
Graph.s = C + C;
Graph.t = C + C + 1;
for ( int i = 0; i < C; i ++ )
Graph.Add_Edge(Graph.s, i + i, 1, 0);
for ( int i = 0; i < C; i ++ )
Graph.Add_Edge(i + i + 1, Graph.t, 1, 0);
Graph.EK();
printf("%lld\n", Graph.mincost);
return 0;
}