洛谷P10336 [UESTCPC 2024] 2-聚类算法

涉及知识点：博弈、贪心

题意

Alice 和 Bob 在玩选点游戏，所有的点在一个 \(k\) 维空间中，他们轮流选走一个点放入自己的集合中，Alice 先手。定义集合 \(S\) 的权值 \(val(S)\) 为集合中点两两之间的 \(k\) 维曼哈顿距离之和。Alice 的得分为 \(val(S_A)-val(S_B)\)，Bob 的得分为 \(val(S_B)-val(S_A)\)，两人都想最大化自己的得分且采用最优策略，请问 Alice 最终得分为多少。

有 \(2n\) 个点，\(1\leq n\times k\leq 10^5\)。

思路

将得分表示出来进行转换，则 Alice 的得分显然为：

\[\sum_{i,j\in S_A,i<j}dis(i,j)-\sum_{i,j\in S_B,i<j} \]

此时两边同时加上 \(\sum_{i,j\in S_B,i>j}dis(i,j)+\sum_{i\in S_A,j\in S_B}dis(i,j)\)：

\[\begin{equation} \begin{aligned} &[\sum_{i,j\in S_A,i<j}dis(i,j)+\sum_{i,j\in S_B,i>j}dis(i,j)+\sum_{i\in S_A,j\in S_B}dis(i,j)]-[\sum_{i,j\in S_B,i<j}dis(i,j)+\sum_{i,j\in S_B,i>j}dis(i,j)+\sum_{i\in S_A,j\in S_B}dis(i,j)] \\ =& [\sum_{i,j\in S_A,i<j}dis(i,j)+\sum_{i,j\in S_B,i<j}dis(i,j)+\sum_{i\in S_A,j\in S_B}dis(i,j)]-[\sum_{i,j\in S_B}dis(i,j)+\sum_{i\in S_A,j\in S_B}dis(i,j)] \\ =& \sum_{i,j\in S_A\cup S_B,i<j}dis(i,j)-\sum_{i\in S_A\cup S_B,j\in S_B}dis(i,j) \end{aligned} \end{equation} \]

因此，Alice 的得分为空间中所有点两两之间的距离之和减去所有点到 \(S_B\) 的距离之和，前者是一个固定值，因此 Alice 想要得分更高，就必须要使得 \(S_B\) 中的点到所有点距离和最小，她得抢在 Bob 前把距离和大的点放到 \(S_A\) 中；然而由于 Bob 的得分是 Alice 的相反数，所以他想使得 \(S_B\) 中的点到所有点距离和最大，他想尽可能取距离和大的点放在 \(S_B\) 中。因此我们将每个点到所有点的距离和算出来并大到小排序，Alice 和 Bob 轮流取最大的点。

另一种很精彩的说法：

将边权化为点权，每个点的点权设为自己到其他所有点的距离之和，这样一来假设两个点 \(a,b\) 分别属于 \(S_A,S_B\) 那么它们点权相减时，它们之间的距离正好可以抵消；假设两个点属于同一个集合，那么它们之间的距离就会被算两次。因此 Alice 的得分即为 \(\frac{\sum S_A-\sum S_B}{2}\)。

那么，如何计算一个点到所有点的距离和呢？肯定不能直接 \(O(n^2k)\) 计算。这里涉及一个小 Trick，由于曼哈顿距离的计算维度之间是不相干扰的，因此可以将每维拆开来计算，将所有点在该维度上的位置从小到大排序，再用前后缀和来计算，这么做是 \(O(kn\log n)\) 的，具体可以参考代码 52-61 行。

代码

用的是此处的答案统计方式。

#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){static char ch[1<<20],*l,*r;return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){T res=0,f=1;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){static char wtbuff[20];static int wtptr;if(x==0){putchar('0');}else{if(x<0){x=-x;putchar('-');}wtptr=0;while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}while(wtptr--) putchar(wtbuff[wtptr]);}if(endch!='\0') putchar(endch);
}
typedef pair<int,int> pii;
typedef long long LL;
const int MAXN=2e5+5;
int n,k;
vector<int>v[MAXN];
vector<pii>dim;
LL dissum[MAXN],ans=0;
int main(){freopen("ys.in","r",stdin);freopen("ys.out","w",stdout);rd(n);rd(k);for(int i=1;i<=2*n;i++){v[i].resize(k);for(int j=0;j<k;j++){rd(v[i][j]);}}for(int i=0;i<k;i++){dim.clear();for(int j=1;j<=2*n;j++) dim.emplace_back(v[j][i],j);sort(dim.begin(),dim.end());LL presum=0;for(int j=0;j<dim.size();j++){dissum[dim[j].second]+=1LL*dim[j].first*j-presum;presum+=dim[j].first;}presum=0;for(int j=dim.size()-1;j>=0;j--){dissum[dim[j].second]+=presum-1LL*dim[j].first*(dim.size()-1-j);presum+=dim[j].first;}}sort(dissum+1,dissum+1+2*n,greater<LL>());for(int i=1;i<=2*n;i+=2)ans+=dissum[i]-dissum[i+1];wt(ans/2);return 0;
}