Codeforces Round #464 (Div. 2) E. Maximize!

98 阅读 0 评论 65 点赞

我是靠谱客的博主过时微笑，最近开发中收集的这篇文章主要介绍Codeforces Round #464 (Div. 2) E. Maximize!，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

You are given a multiset S consisting of positive integers (initially empty). There are two kind of queries:

Add a positive integer to S, the newly added integer is not less than any number in it.
Find a subset s of the set S such that the value $\text{[math]}$ is maximum possible. Here max(s) means maximum value of elements in s, $\text{[math]}$ — the average value of numbers in s. Output this maximum possible value of $\text{[math]}$ .

Input

The first line contains a single integer Q (1 ≤ Q ≤ 5·105) — the number of queries.

Each of the next Q lines contains a description of query. For queries of type 1 two integers 1 and x are given, where x (1 ≤ x ≤ 109) is a number that you should add to S. It's guaranteed that x is not less than any number in S. For queries of type 2, a single integer 2 is given.

It's guaranteed that the first query has type 1, i. e. S is not empty when a query of type 2 comes.

Output

Output the answer for each query of the second type in the order these queries are given in input. Each number should be printed in separate line.

Your answer is considered correct, if each of your answers has absolute or relative error not greater than 10 - 6.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $\text{[math]}$ .

        Examples 
      

          input 
         
           Copy 
         
6
1 3
2
1 4
2
1 8
2

          output 
        
0.0000000000
0.5000000000
3.0000000000

          input 
         
           Copy 
         
4
1 1
1 4
1 5
2

          output 
        
2.0000000000

题意：有一个多重集合（元素可以重复的），初始为空，现有两种操作，1是往集合里添加一个数字x，x一定不小于集合里的任何一个数（这个很重要），2是问这个集合子集中的 max（s） - mean（s）中最大的是多少，max（s）是一个集合中最大的元素，mean（s）是集合的平均值。

思路：因为这个集合是从小到大往里面加数的，很显然答案是这个多重集合中的最大值加上最前面一些数的和，那么加到什么位置为止呢？有这么一句话：如果一个数小于一些数的平均数，那么加上这个数，平均数会变小（我自己编的）。那么显然就有这样一个关系，设前面那些数的和为sum，数量为cnt个，现在集合中有n个数，那么答案就是 a[n] - (sum + a[n] )/ (cnt+1)，那么这个sum怎么算呢，根据前面的结论：sum中已经有cnt个数了，如果 a[cnt+1] < (sum + a[n]) / (cnt+1)，就可以把a[cnt+1]加到sum里，直到a[cnt+1]不符合条件为止。

好了啰嗦了这么多，其实代码很简单。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long

using namespace std;

LL a[500010];

int main(void)
{
    int q,i,j;
    while(scanf("%d",&q)==1)
    {
        LL sum = 0;
        int n = 0;
        int cnt = 0;
        while(q--)
        {
            int op,x;
            scanf("%d",&op);
            if(op == 1)
            {
                n++;
                scanf("%d",&a[n]);
                while(cnt < n && sum + a[n] > a[cnt+1]*(cnt+1))
                {
                    cnt++;
                    sum += a[cnt];
                }
            }
            else
            {
                double ans = a[n] - 1.0*(sum + a[n])/(cnt+1);
                printf("%.6fn",ans);
            }
        }
    }


    return 0;
}