「Codeforces 939E」Maximize!

发表于 | | 阅读次数:
字数统计: 575 字

Description

题目链接：Codeforces 939E

你需要维护一个包含正整数的可重集 $S$ 初始为空，进行 $q$ 次操作，操作分为以下两种：

  1. 往集合 $S​$ 中加入一个正整数 $x​$，保证新加入的整数不小于集合中的数字。
  2. 找出一个 $S$ 的子集 $s$ 使得 $\max(s)-\text{mean}(s)$ 的值最大。其中 $\max(s)$ 指集合 $s$ 中的最大值，$\text{mean}(s)$ 指集合 $s$ 中的平均值。求出这个最大值。

数据范围：$1\le q\le 5\times 10^5​$，$1\le x\le 10^9​$

Solution

平均值这个东西比较麻烦，先解决子集最大值的问题。考虑证明一个结论：原集合 $S$ 的最大值一定属于 $s$。

假设我们已经选择了一个集合 $s’$，其中 $\max(S)\not\in s’$，如果我们把 $\max(s’)$ 换成 $\max(S)$，那么平均值只会增加 $\frac{\max(S)-\max(s’)}{\vert s’\vert}$，而最大值会增加 $\max(S)-\max(s’)$，显然答案更优。

证毕。

这样一来我们只使得平均值最小即可。首先肯定可以贪心地想：把集合 $S$ 中最小的数字放入集合 $s$ 中。而到底要放入多少个数呢？有如下两种情况：

我们设当前平均值为 $a$，下一个可能要放入集合 $s$ 的数为 $x$

  1. 当 $x\le a$ 时，放入 $x$ 会使答案更好，此时 $a$ 会变小。
  2. 当 $x>a$ 时，也就是当 $a$ 变小到一定程序后，再放入 $x$ 会使得答案变差，此时就不应该放入 $x$ 了。

通过分析我们发现，答案在中间某位置取得最优，而两端较劣，很显然是一个单峰函数，可以直接三分求解。

时间复杂度：$O(q\log q)​$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
#include <cstdio>
#include <algorithm>

const int N=5e5+5;
int n,m,a[N];
long long sum[N];

double F(int x) {
    return 1.0*(a[n]+sum[x])/(x+1);
}
int main() {
    scanf("%d",&m);
    while(m--) {
        int opt;
        scanf("%d",&opt);
        if(opt==1) {
            int x;
            scanf("%d",&x);
            a[++n]=x,sum[n]=sum[n-1]+a[n];
        } else {
            int l=1,r=n-1,x=0;
            while(l<=r) {
                int mid=(l+r)>>1;
                if(F(mid)<F(mid-1)) l=(x=mid)+1;
                else r=mid-1;
            }
            printf("%.10lf\n",a[n]-calc(x));
        }
    }
    return 0;
}
0%