题解：CF2157D Billion Players Game

· · 题解

题意

一个数 p\in[L,R]。有 n 个猜测，第 i 个猜测为 p=a_i。对于每一个猜测，你有 3 个选择：忽略它，认为 p \ge a_i，认为 p \le a_i。对于每个没被忽略的猜测，如果你的想法是正确的，那么获得 |p-a_i| 的收益，否则消耗 |p-a_i| 的代价。求可能获得的最小收益的最大值。

解法

拜谢 Sam_Yang 提供解法。

首先一定有一个分界线 i，使得 a_1\sim a_i 取 \ge，a_{i+1} \sim a_n 取 \le（当然也可以忽略）。
其次，如果 a_i 不在 [L,R] 内，那么它的方向是唯一确定的，可以提前累加一些贡献。
有一个事情是最小值要么在 L 取到要么在 R 取到。
现在还没有计算的贡献分为两部分，一个是 [L,R] 区间以外的点到 p 且跨过 [L,R] 区间的贡献，一个是 [L,R] 区间内的点到 p 的贡献。
画个图： 黑色是我们已经算过的贡献（前面说的已被累加），绿色是分界线，红色是 p=L 时没被算到的贡献，橙色是 p=R 时没被算到的贡献。
然后发现中间那些交错的贡献稍微好算一些。由于 p 在一侧，所以它们可以两两匹配，这样正负的贡献便会被抵消。而对于被匹配的两个点 l,r，它们一起能被产生的贡献为 |dis_l-dis_r|，其中 dis_i 是第 i 个点到 p 的距离。
想让这玩意累加最大，让它们从大到小一一匹配就好了。 还有跨过 [L,R] 的贡献。单个的贡献就是 R-L，关键在于有多少个。如果 p=L 那么就是 R 右边的点个数，否则是 L 左边点个数。取个 \min。

我还忘说了一件事。我们希望 p 两端的点都能一个 \ge 一个 \le 的匹配，因为如果不能匹配的话往一边走可以获得不一样的代价。
这个原则在“中间那些交错的贡献”中可以被体现。
但是万一 L 和 R 两边的点们不匹配怎么办？
我们就需要从 [L,R] 区间内借一些点。
如果 L 左边比 R 右边多，那么 p=L，需要从右边借一些点过来，贡献为 a_i-L；否则 p=R，从左边借一些点过来，贡献为 R-a_i。
最后的匹配效果长这样： 

#include<cstdio>
#include<algorithm>
using namespace std;
long long ans,t,n,l,r,s[200005];
int main() 
{
    scanf("%lld",&t);while(t--)
    {
        scanf("%lld%lld%lld",&n,&l,&r),ans=0;
        for(int i=1;i<=n;i++) scanf("%lld",&s[i]);
        sort(s+1,s+n+1);long long ll=1,rr=n;
        while(ll<=n&&s[ll]<=l) ans+=l-s[ll],ll++;
        while(rr>=1&&s[rr]>=r) ans+=s[rr]-r,rr--;
        ans+=min(ll-1,n-rr)*(r-l);
        while(ll>n-rr+1&&ll<=rr) ans+=s[rr]-l,rr--;
        while(ll<n-rr+1&&ll<=rr) ans+=r-s[ll],ll++;
        while(ll<rr) ans+=s[rr]-s[ll],rr--,ll++;
        printf("%lld\n",ans);
    }
}