专栏文章

Codeforces 939E 题解

llzy20091001
CF939E题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minzcf0m
此快照首次捕获于
2025/12/02 10:49
3 个月前
此快照最后确认于
2025/12/02 10:49
3 个月前
查看原文

思路

引理：一定可以选 max⁡(S)\max(S)。考虑反证，设选的最大的数是 tt。若 t≠max⁡(S)t \ne \max(S)，则将 tt 替换为 max⁡(S)\max(S)，有
Δmax⁡(s)=max⁡(S)−tΔavg⁡(s)=max⁡(S)−t∣s∣\Delta \max(s) = \max(S) - t \\ \Delta \operatorname{avg}(s) = \frac{\max(S) - t}{|s|}
显然 Δmax⁡(s)−Δavg⁡(s)≥0\Delta \max(s) - \Delta \operatorname{avg}(s) \ge 0，替换后不劣。
考虑还需要选哪些数，由于 max⁡(s)\max(s) 已经确定，所以我们要让 avg⁡(s)\operatorname{avg}(s) 尽可能小。那么可以在 SS 中从最小到大选，选的时候实时更新 avg⁡(s)\operatorname{avg}(s)。如果碰到了 x∈S ∧ x>avg⁡(s)x \in S \ \wedge \ x > \operatorname{avg}(s) 则停止，因为选 xx 或选比 xx 大的数都会让 avg⁡(s)\operatorname{avg}(s) 变大。
题目保证输入的元素是不降的，这使得 xx 也是不降的，用一个变量记录即可。

实现

为了避免可能的精度问题，我们可以不存储 avg⁡(s)\operatorname{avg}(s) 而是等价地存储 sum⁡(s)\operatorname{sum}(s) 和 ∣s∣|s|。
CPP
#include <iostream>
#include <iomanip>

using namespace std;

const int N = 5e5;

int a[N + 5];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int q, i = 0, j = 0, cnt = 1;
    long long sum = 0;

    cin >> q;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            cin >> a[++i];
            sum += a[i] - a[i - 1];
        }
        else
        {
            while (j + 1 < i && 1LL * a[j + 1] * cnt < sum)
                cnt++, sum += a[++j];
            cout << fixed << setprecision(10) << a[i] - 1.0L * sum / cnt << "\n";
        }
    }

    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...