自动搬运

查看原文

来自洛谷，原作者为

	Lu_xZ NOIP 2024 rp++ | AFO.

搬运于2025-08-24 22:57:03，当前版本为作者最后更新于2024-09-27 17:54:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

官方题解做法。

$$\begin{aligned} & \sum_{i < j\in S_a} \text{dist}(p_i, p_j) - \sum_{i < j \in S_b} \text{dist}(p_i, p_j)\\ \\ =& \bigg(\sum_{i < j\in S_a} \text{dist}(p_i, p_j) + \sum_{i < j\in S_b} \text{dist}(p_i, p_j) + \sum_{i \in S_a, j\in S_b} \text{dist}(p_i, p_j) \bigg) - \bigg(\sum_{i < j \in S_b} \text{dist}(p_i, p_j) + \sum_{i > j\in S_b} \text{dist}(p_i, p_j) + \sum_{i \in S_a, j\in S_b} \text{dist}(p_i, p_j)\bigg)\\ \\ =& \sum_{i, j \in U} \text{dist}(p_i, p_j) - \sum_{i \in U,\ j \in S_b} \text{dist}(p_i, p_j) \end{aligned} $$

前一项是定值，后一项只与 $S_b$ 有关。

对 $A$ 来说想让最大的点不计入贡献，对 $B$ 来说要尽可能选大的点。

因此每个人的决策就是取当前到所有点距离和最大的点。

#include<bits/stdc++.h>
#define eb emplace_back
#define ep emplace
using namespace std;

using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N, K; cin >> N >> K;
	N *= 2;
	vector a(N, vector<int>(K));
	for(int i = 0; i < N; ++ i) {
		for(int j = 0; j < K; ++ j) {
			cin >> a[i][j];
		}
	}
	vector<ll> d(N);
	for(int k = 0; k < K; ++ k) {
		vector<int> id(N);
		iota(id.begin(), id.end(), 0);
		sort(id.begin(), id.end(), [&](int i, int j) {
			return a[i][k] < a[j][k];
		});
		ll sum = 0;
		for(int i = 0; i < N; ++ i) {
			int j = id[i];
			d[j] += ll(i) * a[j][k] - sum;
			sum += a[j][k]; 
		}
		reverse(id.begin(), id.end());
		sum = 0;
		for(int i = 0; i < N; ++ i) {
			int j = id[i];
			d[j] += sum - ll(i) * a[j][k];
			sum += a[j][k]; 
		}
	}
	sort(d.begin(), d.end(), [&](ll x, ll y) {
		return x > y;
	});
	ll ans = 0;
	for(int i = 0; i < N; ++ i) {
		ans += d[i];
	}
	ans /= 2;
	for(int i = 1; i < N; i += 2) ans -= d[i];
	cout << ans;
	return 0;
}