【解题报告】CF939E

题目链接

http://codeforces.com/problemset/problem/939/E

思路

贪心

这道题目发现，要选的数字的最大值的减去选的数字平均值最大，我们可以yy出来我们每次加入的新的数字都要加进去（因为单调递增地加入数字

然后我们从前面加数字，然后加的数字如果能使平均数更小，那我们即一直加下去，否则我们不加，这样贪心就行了

证明不太会

然后要开long long

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
32
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
long long T,s[500005];
long long len,ans,tot;
int main()
{
	cin>>T;
	while(T--)
	{
		int op,x;
		cin>>op;
		if(op==1)
		{
			cin>>x;
			s[++len]=x;
			while(((double)ans+(double)s[len])/((double)tot+1)>((double)ans+(double)s[len]+s[tot+1])/((double)tot+2))
			{
				tot++;
				ans+=s[tot];
			}
		}
		else
		{
			printf("%lf\n",(double)s[len]-((double)ans+(double)s[len])/((double)tot+1));
		}
	}
	return 0;
}