题解：P10336 [UESTCPC 2024] 2-聚类算法

Sunnysky0 · 2025-07-03 15:07:20 · 题解

定义 s_{i}=\sum_{j=1}^{2 n} \operatorname{dist}(i, j) 为总距离和。

那么有 \operatorname{val}\left(S_{a}\right)-\operatorname{val}\left(S_{b}\right)=\frac{1}{2} \sum_{i=1}^{2 n} x_{i} s_{i} 。

其中 x_i = \begin{cases} +1, & i \in S_a \\ -1, & i \in S_b \end{cases} 。

这一博弈的最优策略非常简单：双方都应在自己回合拿走当前剩余 s_i 中最大的一个。结果就是把所有从大到小排序后交替取走。 将所有点按每个维度的坐标提取出来并排序，前缀和即可求出 s_i 。

代码：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int half, k; cin >> half >> k;
    int n = half * 2;
    vector<vector<int>> pos(n, vector<int>(k));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            cin >> pos[i][j];
    vector<ll> s(n, 0);
    for (int dim = 0; dim < k; dim++) {
        vector<pair<int,int>> vr; vr.reserve(n);
        for (int i = 0; i < n; i++) vr.emplace_back(pos[i][dim], i);
        sort(vr.begin(), vr.end(), [](auto &a, auto &b){ return a.first < b.first; });
        vector<ll> p(n+1, 0);
        for (int i = 0; i < n; i++)
            p[i+1] = p[i] + vr[i].first;
        for (int i = 0; i < n; i++) {
            ll coord = vr[i].first;
            int idx = vr[i].second;
            ll left_sum = coord * i - p[i];
            ll right_sum = (p[n] - p[i+1]) - coord * (n - i - 1);
            s[idx] += left_sum + right_sum;
        }
    }
    sort(s.begin(), s.end(), greater<ll>());
    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans += (i % 2 == 0 ? 1 : -1) * s[i];
    cout << (ans / 2) << "\n";
    return 0;
}