Codeforces 939E 题解

· · 题解

思路

引理：一定可以选 \max(S)。考虑反证，设选的最大的数是 t。若 t \ne \max(S)，则将 t 替换为 \max(S)，有

\Delta \max(s) = \max(S) - t \\ \Delta \operatorname{avg}(s) = \frac{\max(S) - t}{|s|}

显然 \Delta \max(s) - \Delta \operatorname{avg}(s) \ge 0，替换后不劣。

考虑还需要选哪些数，由于 \max(s) 已经确定，所以我们要让 \operatorname{avg}(s) 尽可能小。那么可以在 S 中从最小到大选，选的时候实时更新 \operatorname{avg}(s)。如果碰到了 x \in S \ \wedge \ x > \operatorname{avg}(s) 则停止，因为选 x 或选比 x 大的数都会让 \operatorname{avg}(s) 变大。

题目保证输入的元素是不降的，这使得 x 也是不降的，用一个变量记录即可。

实现

为了避免可能的精度问题，我们可以不存储 \operatorname{avg}(s) 而是等价地存储 \operatorname{sum}(s) 和 |s|。

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