题解：CF2157D Billion Players Game

· · 题解

提供一种单组数据 \mathcal O(n) 的做法。

先把绝对值去掉，这样每个下注建议就是在 \{x-a_i,a_i-x,0\}（假设最终排名为 x）选一个。

若选择 \{x-a_i,a_i-x,0\} 的建议集合分别为 A,B,C，那么最终收益为：

f(x)=\sum_{i\in A} (x-a_i)+\sum_{i\in B} (a_i-x)

将 x 拆出来：

f(x)=(|A|-|B|)x+\sum_{i\in B} a_i-\sum_{i\in A} a_i

要求的答案即 \min_{i=l}^r f(i)。

考虑让斜率 |A|-|B| 的绝对值尽可能小，并且 \sum_{i\in B} a_i-\sum_{i\in A} a_i 尽可能大，这样显然是最优的。

于是可以将 a 数组排序，前一半取 x-a_i，后一半取 a_i-x。此时 x 为中位数时有最小值。

发现前一半的 x-a_i 和后一半的 a_i-x 在 x 取中位数时都是 |a_i-x|，因此可以不用排序，\mathcal O(n) 求出中位数即可。

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,l,r,a[N];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        long long ans=0;
        scanf("%d%d%d",&n,&l,&r);
        for(int i=1;i<=n;i++) scanf("%d",a+i);
        nth_element(a+1,a+(n+1>>1),a+n+1);
        int x=a[n+1>>1];x=max(x,l),x=min(x,r);
        for(int i=1;i<=n;i++) ans+=abs(a[i]-x);
        printf("%lld\n",ans);
    }
    return 0;
}