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

· · 题解

官方题解做法。

\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;
}