• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【解题报告】CF939E

开发技术 开发技术 3天前 3次浏览

【解题报告】CF939E

题目链接

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

思路

贪心

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

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

证明不太会

然后要开long long

#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("%lfn",(double)s[len]-((double)ans+(double)s[len])/((double)tot+1));
		}
	}
	return 0;
}

程序员灯塔
转载请注明原文链接:【解题报告】CF939E
喜欢 (0)