专栏文章

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

SSunnysky0
P10336题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miozr9it
此快照首次捕获于
2025/12/03 03:48
3 个月前
此快照最后确认于
2025/12/03 03:48
3 个月前
查看原文
定义 si=∑j=12ndist⁡(i,j)s_{i}=\sum_{j=1}^{2 n} \operatorname{dist}(i, j) 为总距离和。
那么有 val⁡(Sa)−val⁡(Sb)=12∑i=12nxisi\operatorname{val}\left(S_{a}\right)-\operatorname{val}\left(S_{b}\right)=\frac{1}{2} \sum_{i=1}^{2 n} x_{i} s_{i} 。
其中 xi={+1,i∈Sa−1,i∈Sbx_i = \begin{cases} +1, & i \in S_a \\ -1, & i \in S_b \end{cases} 。
这一博弈的最优策略非常简单：双方都应在自己回合拿走当前剩余 sis_i 中最大的一个。结果就是把所有从大到小排序后交替取走。 将所有点按每个维度的坐标提取出来并排序，前缀和即可求出 sis_i 。
代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...