CF1765J Hero to Zero 题解

题意

给出长为 \(n\) 数组 \(a,b\)，令 \(c_{i,j}=|a_i-b_j|\)。

每次可以花 \(1\) 的代价让矩阵 \(c\) 的一行或一列或一个格子减 \(1\)，也可以花 \(-1\) 的代价让一行或一列加 \(1\)。

求让矩阵清零的最小代价。

题解

后面加 \(1\) 的操作显然没什么用。

每次减一行或一列都能减 \(n\)，一个格子只能减 \(1\)。所以需要最大化减一行或一列的次数。

设减了 \(p_i\) 次第 \(i\) 行，\(q_i\) 次第 \(j\) 列。

需要在满足限制 \(p_i+q_j\le c_{i,j}\) 的情况下最大化 \(\sum p_i+\sum q_j\)。

发现把限制乘个 \(-1\) 就变成和 KM 算法顶标一样的限制了。所以求的就是最小权完美匹配。

排个序对位匹配即可。随便算一算。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
	int n;
	scanf("%d",&n);
	vector<int> a(n),b(n);
	for(int&x:a) scanf("%d",&x);
	for(int&x:b) scanf("%d",&x);
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	ll ans=0;
	for(int i=0;i<n;i++)
		ans+=1ll*n*(a[i]+b[i])-
		2ll*a[i]*(b.end()-lower_bound(b.begin(),b.end(),a[i]))-
		2ll*b[i]*(a.end()-upper_bound(a.begin(),a.end(),b[i]));
	for(int i=0;i<n;i++) ans-=(n-1ll)*abs(a[i]-b[i]);
	printf("%lld\n",ans);
	return 0;
}