Codeforces 939E Maximize ( 三分 || 二分 )

题意 : 给出两个操作，① 往一个序列集合（初始为空）里面不降序地添加数字、② 找出当前序列集合的一个子集使得（子集的最大元素） - （子集的平均数）最大并且输出这个最大差值

分析 :

首先关注到 ① 操作是有序地添加数

然后为了回答 ② 的问询，来分析一波

直觉告诉我们，要最大化差值，选取的子集最大元素应当越大越好

这一点是对的，具体的证明可以看 CF 的官方题解

那么也就是说选出的子集里面必定有当前序列集合的最大值元素

然后为了使（子集的平均数）越小，直觉又告诉我们

需要贪心地选择小的元素加入子集，这一点是显然的

仔细一想就能发现，如果我们从小到大地将元素加入子集

子集的平均数肯定是先减后增，是个凹函数

又因为是序列有序，所以我们可以去三分序列的前缀和数组寻找凹点

最后的答案就是（集合序列最大值） - （凹点的平均值）

至于二分解法，也同样是和上面一个道理

我们可以去二分前缀和数组的一个位置，假设为 POS

如果算出来的平均值比 POS+1 这个位置的元素更大

说明加入 POS+1 这个元素肯定更优，最后一直二分到合理位置就是答案了

具体看代码

二分 1231ms

#include<bits/stdc++.h>
#define LL long long
using namespace std;
;
vector<LL> arr;
LL Presum[maxn];

inline void GetAns()
{
    , R = arr.size()-, idx = ;
    double avg;
    while(L <= R){
        ;
        avg = (] + Presum[mid]) / ();
        ]) L = mid + ;///平均值比后面的元素更大，说明添加进 mid+1 这个元素肯定更优
        , idx = mid;
    }

    avg = (] + Presum[idx]) / ();
    ] - avg;
    printf("%.9f\n", ans);
}

int main(void)
{
    int Q;
    scanf("%d", &Q);
    while(Q--){
        int command;
        scanf("%d", &command);
        ){
            LL tmp;
            cin>>tmp;
            arr.push_back(tmp);
            Presum[arr.size()-] = ((arr.size()- < ) ?  : Presum[arr.size()-]) + tmp;
        }else GetAns();
    }
    ;
}

二分

三分 514ms

#include<bits/stdc++.h>
#define LL long long
using namespace std;
;
vector<LL> arr;
LL Presum[maxn];

double Fun(int pos)
{ ] + Presum[pos]) / (); }

double GetAns()
{
    , R = arr.size() - ;
    ){
        ;
        ;
        if( Fun(mid) > Fun(mmid) ) L = mid;
        else R = mmid;
    }
    ] - Fun(Fun(L) > Fun(R) ? R : L);
}

int main(void)
{
    int Q;
    scanf("%d", &Q);
    while(Q--){
        int command;
        scanf("%d", &command);
        ){
            LL tmp;
            scanf("%I64d", &tmp);
            arr.push_back(tmp);
            Presum[arr.size()-] = (arr.size()- <  ?  : Presum[arr.size()-]) + tmp;
        }else{
            printf("%.9f\n", GetAns());
        }
    }
    ;
}

三分

巴特西

Codeforces 939E Maximize ( 三分 || 二分 )

最新文章

热门文章