Maximize

题意:整个程序有2种操作,操作1将一个元素放入集合S中,且保证最新插入的元素不小于上一次的元素, 操作2 找到集合S中的某个子集合, 使得 集合中最大的元素减去平均数的值最大。

题解:找子集合的时候将整个几个分成2边, 左边为前i个数, 右边为最新插入的数。 那么我们就可以想到, 每次插入新的元素时, 对应最新这个元素的 ans值 的左边部分的个数不会少于前面那个i, 然后我们继续往右边走找到临界的位置就好了, 每次如果左边的值小于现在的平均值就能放入集合中。

代码

 #include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstdio>
#define LL long long
#define ULL unsigned LL
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fi first
#define se second
using namespace std;
const int N = 5e5+;
LL a[N];
int main(){
int Q;
scanf("%d",&Q);
int t;
LL sum = ;
int cnt = , tot = ;
while(Q--){
scanf("%d",&t);
if(t == ){
printf("%.7f\n",a[tot]-1.0*(a[tot]+sum)/cnt);
}
else {
scanf("%I64d", &a[++tot]);
while(cnt < tot){
if(a[cnt]*cnt < sum+a[tot])
sum += a[cnt++];
else break;
}
}
}
return ;
}

最新文章

  1. MyBatis学习(一)、MyBatis简介与配置MyBatis+Spring+MySql
  2. asp.net+nopi生成Excel遇到设置单元格值null问题
  3. spark调试
  4. Orchard SQLite v1.7.2
  5. WCF入门(二)-----实战开发
  6. Jeally Bean中MonekyRunner 帮助文件
  7. Bottle 中文文档
  8. C# 操作Excel (二)
  9. OpenCV:Mat元素访问方法、演出、代码的复杂性和安全性分析
  10. JavaScript中国象棋程序(0) - 前言
  11. 蓝桥杯比赛javaB组练习《饮料换购》
  12. BZOJ 1488: [HNOI2009]图的同构 [Polya]
  13. IOS开发中关于runtime的认识
  14. Odd-e CSD Course Day 4
  15. gitlab安装随记
  16. android设备如何进入深度休眠还能继续使用定时器【求解】
  17. BZOJ4255 : Keep Fit!
  18. SharePoint 站点导航Web部件
  19. css3动画属性系列之transform细讲scale缩放
  20. SpringCloud统一配置之使用配置

热门文章

  1. 异步请求xhr、ajax、axios与fetch的区别比较
  2. 免安装版tomcat安装成服务
  3. Java课堂 动手动脑6
  4. 如何阅读JDK源码
  5. idea 新建不了servlet文件 方法(1)
  6. python异常处理-异常捕获-抛出异常-断言-自定义异常-UDP通信-socketserver模块应用-3
  7. Hadoop学习(9)-spark的安装与简单使用
  8. zookeeper基本知识入门(一)
  9. 算法与数据结构基础 - 折半查找(Binary Search)
  10. Oracle中的通用函数