文档章节

xjoj挖金矿(二分验证)

Loi_DL
 Loi_DL
发布于 2016/11/03 07:41
字数 280
阅读 8
收藏 0

 

由于数据范围比较迷,所以数组开一维就好,即二维抽象成一维。注意精度,注意long long,二分答案,sum[i][j]记录第几列深度为多少的前缀和,h[i]记录一共挖了多少深度。那么一定有 平均值x==sum[i][j]/h[i]>=0,移项化简易得sum[i][j]-h[i]*x>=0。二分验证这个式子成立即可。 

当时做题的时候比较迷,打了一个错误的暴力。


 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int h,n,num[110000];
long long sum[110000];
double l=0,r,mid,s,mx;
int main()
{
	scanf("%d%d",&n,&h);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=h;j++)
	{
		int k=(i-1)*h+j;
		scanf("%d",&num[k]);	
		if(num[k]>r) r=num[k];
		if(j!=1) sum[k]=sum[k-1]+num[k];
		else sum[k]=num[k];
	}
	while (r-l>0.000001)
	{
		mid=(r+l)/2;
		s=0;
		for(int i=1;i<=n;i++)
		{
			mx = -2147483645;
			for(int j=1;j<=h;j++)
			mx=max(mx,sum[(i-1)*h+j]-j*mid);
			s+=mx;
		}
		if(s>=0) l=mid;
		else r=mid;	
	}
	printf("%.4lf",mid);
	return 0;
}
/*
4 3
4 3 3
5 1 6
2 6 1
3 2 9
*/

 

© 著作权归作者所有

上一篇: 重载 高精度
下一篇: 胡策tayz DAY2
Loi_DL
粉丝 0
博文 60
码字总数 48692
作品 0
莱芜
私信 提问
看动画轻松理解“递归”与“动态规划”

作者 | 程序员小吴 来源 | 五分钟学算法 在学习「数据结构和算法」的过程中,因为人习惯了平铺直叙的思维方式,所以「递归」与「动态规划」这种带循环概念(绕来绕去)的往往是相对比较难以理...

AI科技大本营
2018/12/26
0
0
MySQL索引工作原理问题

MYSQL环境为存储引擎MyISam,现在有这样一个查询语句:select * from A where A.X='张三',其中X为索引列,现在的问题是,mysql在进行索引查询时如何去查找索引值='张三'的信息的?我们知道mysql...

雪沐清风
2016/03/31
210
1
漫画:什么是动态规划?(整合版)

———————————— 题目: 有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。 比如,每次走1级台阶,一共走10步,这是其...

群星纪元
04/13
23
0
一个简单的猜拳小游戏(C语言实现)

小伙伴们,对C语言编程有疑问的,可以加微信交流:poo_poo或者扫描我的头像,验证时请注明是“知友” 这个小游戏的原题是“C primer plus 5版” 第8章编程题4。 一、题目描述 二、题目及思路...

石家的鱼
2017/07/28
0
0
[Deep-Learning-with-Python]基于Keras的imdb数据集电影评论情感二分类

IMDB数据集下载速度慢,可以在我的repo库中找到下载,下载后放到~/.keras/datasets/目录下,即可正常运行。 电影评论分类:二分类 二分类可能是机器学习最常解决的问题。我们将基于评论的内容...

七八音
2018/07/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Replugin借助“UI进程”来快速释放Dex

public static boolean preload(PluginInfo pi) { if (pi == null) { return false; } // 借助“UI进程”来快速释放Dex(见PluginFastInstallProviderProxy的说明) return PluginFastInsta......

Gemini-Lin
今天
4
0
Hibernate 5 的模块/包(modules/artifacts)

Hibernate 的功能被拆分成一系列的模块/包(modules/artifacts),其目的是为了对依赖进行独立(模块化)。 模块名称 说明 hibernate-core 这个是 Hibernate 的主要(main (core))模块。定义...

honeymoose
今天
4
0
CSS--属性

一、溢出 当内容多,元素区域小的时候,就会产生溢出效果,默认是纵向溢出 横向溢出:在内容和容器之间再套一层容器,并且内部容器要比外部容器宽 属性:overflow/overflow-x/overflow-y 取值...

wytao1995
今天
4
0
精华帖

第一章 jQuery简介 jQuery是一个JavaScript库 jQuery具备简洁的语法和跨平台的兼容性 简化了JavaScript的操作。 在页面中引入jQuery jQuery是一个JavaScript脚本库,不需要特别的安装,只需要...

流川偑
今天
7
0
语音对话英语翻译在线翻译成中文哪个方法好用

想要进行将中文翻译成英文,或者将英文翻译成中文的操作,其实有一个非常简单的工具就能够帮助完成将语音进行翻译转换的软件。 在应用市场或者百度手机助手等各大应用渠道里面就能够找到一款...

401恶户
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部