[CF2157D] Billion Players Game 题解

实际上这个绝对值没啥用，先把这个东西去掉，这样对于

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

，于是对增量排序然后贪心即可。

k<0

的做法时对称的，对于

k=0

只需要把这个情况加进

k>0,k<0

任意一个即可。时间复杂度为排序的

\mathcal{O}(n\log n)

。

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;
}

[CF2157D] Billion Players Game 题解

文章操作

相关推荐

评论

[CF2157D] Billion Players Game 题解