[CF2157D] Billion Players Game 题解
aeiouaoeiu
·
·
题解
实际上这个绝对值没啥用，先把这个东西去掉，这样对于 a_i 的决策就变成了 \{0,a_i-p,p-a_i\} 选一个。
注意到最终得到的结果实际上是一个关于 p 的一次函数，设为 kp+b，则可以根据 k 的正负分类讨论。
若 k>0，则求答案时 p 取 l，那么现在的问题就是，对于 i，要从 [0,a_i-l,l-a_i] 中选一个，对应的标记分别为 [0,-1,1]，现在要使标记之和 >0，求最大权值。
可以发现标记由 x\to x+1 时，权值的增量为 l-a_i，于是对增量排序然后贪心即可。
::::info[code]
```cpp
#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const ll maxn=1000007,ee=1e18;
ll n,l,r,a[maxn];
vector<ll> vec;
ll solve1(ll x){
ll cur=0;
vec.clear();
for(ll i=1;i<=n;i++) cur+=a[i]-x,vec.pb(x-a[i]),vec.pb(x-a[i]);
sort(vec.begin(),vec.end(),greater<ll>());
for(ll i=0;i<n;i++) cur+=vec[i];
for(ll i=n;i<2*n;i++)if(vec[i]>=0) cur+=vec[i];
return cur;
}
ll solve2(ll x){
ll cur=0;
vec.clear();
for(ll i=1;i<=n;i++) cur+=x-a[i],vec.pb(a[i]-x),vec.pb(a[i]-x);
sort(vec.begin(),vec.end(),greater<ll>());
for(ll i=0;i<n;i++) cur+=vec[i];
for(ll i=n;i<2*n;i++)if(vec[i]>=0) cur+=vec[i];
return cur;
}
int main(void){
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
ll T=1; cin>>T;
for(;T--;){
cin>>n>>l>>r;
for(ll i=1;i<=n;i++) cin>>a[i];
cout<<max(solve1(l),solve2(r))<<"\n";
}
return 0;
}
```
::::