[COCI 2011/2012 #5] EKO / 砍树 (二分)不开龙永远的痛!

long

long

long

long

long

//应该以最高的树为基准二分

初次尝试:

 #include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;
//应该以最高的树为基准二分
int n;
int m;
int a[1000010];
int maxx=-1;
int minn=100000;

bool check(int mid){
	int high = 0;
	for(int i=0;i<n;i++){
		if(a[i] > mid){
			high += (a[i] - mid);
		}
	}
	if(high < m) return false;
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		if(a[i] > maxx) maxx = a[i];//找到最高的 
		if(a[i] < minn) minn = a[i];
	}	
//	printf("%d %d\n",minn,maxx);
	 
//	cout<<"****"<<endl;
	int l= minn,r=maxx;
	while(l<r){
		//找右端点,右端小左
		 int mid = l+r+1 >> 1;
		 if(check(mid)){
		 	l = mid;
		// 	printf("llll%d\n",l);
		 } 
		 else {
		 	r = mid - 1; 
		// 	printf("rrrr%d\n",r);
		 }
		 	
	}
	cout<<l<<endl;
	return 0;
} 

结果:

AC代码:因为M的数据范围是2的9次方,需要开longlong,对应的判断函数里high的也要开成longlong。

 #include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;
//应该以最高的树为基准二分
int n;
long long m;
int a[1000010];
int maxx=-1;
int minn=100000;

bool check(int mid){
	long long high = 0;
	for(int i=0;i<n;i++){
		if(a[i] > mid){
			high += (a[i] - mid);
		}
	}
	if(high < m) return false;
	return true;
}
int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		if(a[i] > maxx) maxx = a[i];//找到最高的 
		if(a[i] < minn) minn = a[i];
	}	
//	printf("%d %d\n",minn,maxx);
	 
//	cout<<"****"<<endl;
	int l= minn,r=maxx;
	while(l<r){
		//找右端点,右端小左
		 int mid = l+r+1 >> 1;
		 if(check(mid)){
		 	l = mid;
		// 	printf("llll%d\n",l);
		 } 
		 else {
		 	r = mid - 1; 
		// 	printf("rrrr%d\n",r);
		 }
		 	
	}
	cout<<l<<endl;
	return 0;
} 

结果:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515295.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

图的深度优先遍历DFS得到各节点的度

在 一文中&#xff0c;我们通过了广度优先搜索来得到图结构中各结点的度&#xff0c;在这一篇文章中&#xff0c;我们要通过深度优先搜索来得到图结构中各结点的度。 初始化 初始化&#xff0c;在下面的代码中&#xff0c;我们创建了一个具有6个结点的图结构&#xff0c;以及…

YOLO电动车检测识别数据集:12617张图像,yolo标注完整

YOLO电动车检测识别数据集&#xff1a;12617张图像&#xff0c;电动车一类&#xff0c;yolo标注完整&#xff0c;部分图像应用增强。 适用于CV项目&#xff0c;毕设&#xff0c;科研&#xff0c;实验等 需要此数据集或其他任何数据集请私信

【调度工具】Azkaban用户手册

目录 一、概述 1.1 Azkaban 是什么 1.2 Azkaban 特点 1.3 Azkaban 与 Oozie 对比 功能 工作流定义 工作流传参 定时执行 资源管理 工作流执行 工作流管理 1.4 Azkaban 运行模式及架构 Azkaban 三大核心组件 Azkaban有两种部署方式 Azkaban Web Server Azkaban …

简约轻量-失信录系统源码

失信录系统-最新骗子收录查询系统源码 首页查询&#xff1a; 举报收录页&#xff1a; 后台管理页&#xff1a; 失信录系统 V1.0.0 更新内容&#xff1a; 1.用户查询,举报功能 2.界面独立开发 3.拥有后台管理功能 4.xss,sql安全过滤 5.平台用户查询 6.用户中心&#xff08;待完…

IO流:字节流、字符流、缓冲流、转换流、数据流、序列化流 --Java学习笔记

目录 IO流 IO流的分类 IO流的体系 字节流&#xff1a; 1、Filelnputstream(文件字节输入流) 2、FileOutputStream(文件字节输出流) 字节流非常适合做一切文件的复制操作 复制案例&#xff1a; try-catch-finally 和 try-with-resource 字符流 1、FileReader(文件字符…

JimuReport 积木报表

一款免费的数据可视化报表&#xff0c;含报表和大屏设计&#xff0c;像搭建积木一样在线设计报表&#xff01;功能涵盖&#xff0c;数据报表、打印设计、图表报表、大屏设计等&#xff01; Web 版报表设计器&#xff0c;类似于 excel 操作风格&#xff0c;通过拖拽完成报表设计…

C#学生信息管理系统

一、引言 学生信息管理系统是现代学校管理的重要组成部分&#xff0c;它能够有效地管理学生的基本信息、课程信息、成绩信息等&#xff0c;提高学校管理的效率和质量。本文将介绍如何使用SQL Server数据库和C#语言在.NET平台上开发一个学生信息管理系统的课程设计项目。 二、项…

前端学习<四>JavaScript基础——02-JavaScript入门:hello world

开始写第一行 JavaScript&#xff1a;hello world JS 代码的书写位置在哪里呢&#xff1f;这个问题&#xff0c;也可以理解成&#xff1a;引入 JS 代码&#xff0c;有哪几种方式&#xff1f;有三种方式&#xff1a;&#xff08;和 CSS 的引入方式类似&#xff09; 行内式&…

msyql 查看和修改字符集的方法

在插入或修改数据的时候&#xff0c;报字符集的错误&#xff0c;中文的无法进行插入修改。比如&#xff1a; update users set user_name关羽 where user_id2; 报错信息&#xff1a; ERROR 1366 (HY000): Incorrect string value: /xB9/xD8/xD3/xF0 for column user_name at …

2024年学浪视频下载器

学浪视频官方没有提供下载选项&#xff0c;但又有很多人需要学浪视频下载器&#xff0c;于是我就开发了这么一款软件&#xff0c;学浪视频下载器:小浪助手.exe 我把学浪下载器打包成压缩包&#xff0c;有需要的自己取一下 链接&#xff1a;https://pan.baidu.com/s/1y7vcqILT…

Google Chrome 常用设置

Google Chrome 常用设置 References 转至网页顶部 快捷键&#xff1a;Home 转至内容设置 chrome://settings/content 清除浏览数据 历史记录 -> 清除浏览数据 关于 Chrome 设置 -> 关于 Chrome chrome://settings/help References [1] Yongqiang Cheng, https:/…

保健品wordpress外贸模板

保健品wordpress外贸模板 健康保养保健品wordpress外贸模板&#xff0c;做大健康行业的企业官方网站模板。 https://www.jianzhanpress.com/?p3514

NucleiStudio下longan nano烧录官方例程

longan nano烧录官方例程 一、准备工作二、编译程序三、器件连接四、烧录程序 IDE:NucleiStudio202009 开发板:longan nano gd32vf103c8t6 一、准备工作 1、下载IDE 芯来科技官网下载NucleiStudio 2、下载烧录器 https://dl.sipeed.com/shareURL/LONGAN/LonganPi3H 网盘链接 …

达梦配置ODBC连接

达梦配置ODBC连接 基础环境 操作系统&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) 数据库版本&#xff1a;DM Database Server 64 V8 架构&#xff1a;单实例1 下载ODBC包 下载网址&#xff1a;https://www.unixodbc.org/ unixODBC-2.3.0.tar.gz2 编译并…

【Qt 学习笔记】认识QtSDK中的重要工具

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ 认识QtSDK中的重要工具 文章编号&#xff1a;Qt 学习笔记 / 03 文章目…

MySQL安装卸载-Linux

目录 1.概述 2.安装 2.1.上传 2.2.解压 ​​​​​​​2.3.安装 ​​​​​​​2.4.启动服务 ​​​​​​​2.5.查询临时密码 ​​​​​​​2.6.修改临时密码 ​​​​​​​2.7.创建用户 ​​​​​​​2.8.分配权限 ​​​​​​​2.9.重新链接 3.卸载 3.1.停…

A53 cache的架构解读

快速链接: 【精选】ARMv8/ARMv9架构入门到精通-[目录] &#x1f448;&#x1f448;&#x1f448; 引流关键词:缓存,高速缓存,cache, CCI,CMN,CCI-550,CCI-500,DSU,SCU,L1,L2,L3,system cache, Non-cacheable,Cacheable, non-shareable,inner-shareable,outer-shareable, optee、…

【C++】C++11类的新功能

&#x1f440;樊梓慕&#xff1a;个人主页 &#x1f3a5;个人专栏&#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》 &#x1f31d;每一个不曾起舞的日子&#xff0c;都是对生命的辜负 目录 前言 默认成员函数 类成…

shell的编写

文章目录 1.框架2.命令行3.获取用户命令字符串4.命令行字符串分割5.执行命令和内建命令6.完整代码&#xff1a; 1.框架 我们知道shell是一直存在的&#xff0c;所以首先我们第一步就是要搭建一个框架&#xff0c;使其一直存在。 那么也很简单&#xff0c;一个while循环就可以完…

intellij idea 使用git的 cherry pick 摘取其他分支的comment

cherry pick 摘取其他分支的comment 如果想把 feature_v1.0 分支的comment 摘到 feature_v1.0_new 分支上&#xff0c; 先切换到 feature_v1.0_new分支&#xff0c;这一步不能少了。然后点击 下面菜单栏的 git&#xff0c;点击Local Changes旁边的 Log&#xff0c;这时能看到…