二分答案(砍树,借教室)

二分的两种情况附代码:

 二分查找条件:单调,二段性

例题1:P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

上代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int a[N],b[N];
int n;
long long m;
	
bool check(int h)
{
	long long sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=max(0,a[i]-h);
	}
	if(sum<m)
	return false;
	return true;
}
int main(){
	
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	int l=0,r=400000;
	while(l<r)
	{
		int mid=(l+r+1)/2;
		if(check(mid))
		l=mid;
		else
		r=mid-1;
	}
	cout<<l;
	return 0;
}

例题2:503. 借教室 - AcWing题库

上代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
long long r[N],d[N],s[N],t[N],b[N];
long long n,m;

bool check(int mid)
{
	for(long long i=1;i<=n;i++)
	b[i]=r[i]-r[i-1];
	
	for(long long i=1;i<=mid;i++)
	{
		b[s[i]]-=d[i];
		b[t[i]+1]+=d[i];
	}
	
	for(long long i=1;i<=n;i++)
	{
		b[i]+=b[i-1];
		if(b[i]<0)
		return true;
	}
	return false;
}
int main()
{
	
	cin>>n>>m;
	for(long long i=1;i<=n;i++)
	{
		cin>>r[i];
	}
	for(long long i=1;i<=m;i++)
	{
		cin>>d[i]>>s[i]>>t[i];
	}
	long long l=1,r=m+1;
	while(l<r)
	{
		long long  mid=(l+r)/2;
		if(check(mid))
		r=mid;
		else
		l=mid+1;
	}
	if(r==m+1)
	cout<<0<<endl;
	else
	cout<<-1<<endl<<r<<endl;
	return 0;
	
}

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

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

相关文章

【数据结构与算法】归并排序(详解:递归与非递归的归并排序 | 赠:冒泡排序和选择排序)

前言 本篇博客会对排序做一个收尾&#xff0c;将最经典的七大排序介绍完毕。 这次的重点正如标题&#xff0c;主要讲的是归并排序&#xff0c;还会带过相对简单很多的冒泡排序和选择排序。在最后还会给这七大排序做出一个时间复杂度和稳定性展示的总结收尾。同时&#xff0c;这…

钉钉事件订阅前缀树算法gin框架解析

当钉钉监测到发生一些事件&#xff0c;如下图 此处举例三个事件user_add_org、user_change_org、user_leave_org&#xff0c;传统的做法是&#xff0c;我们写三个if条件&#xff0c;类似下图 这样字符串匹配效率比较低&#xff0c;于是联想到gin框架中的路由匹配算法&#xff0…

非写代码无以致远

标题党一下&#xff0c;本篇文章主要汇总了一些代码题&#xff0c;让大家写一些代码练习一下吧&#xff01; 变种水仙花_牛客题霸_牛客网 (nowcoder.com) #include<stdio.h> int main() {for (int i 10000; i < 99999; i) {int sum 0;for (int j 10; j < 1000…

码农失业倒计时?全球首个大厂AI程序员来了

进入互联网时代&#xff0c;程序员作为高收入职业的代表&#xff0c;长久以来一直是众多求职者梦寐以求的工作方向。程序员们凭借其对计算机科学的深刻理解和技术创新能力&#xff0c;不仅推动了科技的进步&#xff0c;也为自己赢得了可观的经济回报。 然而&#xff0c;随着人…

AD20全流程的使用笔记

目录 首先一个完整的AD工程文件需要我们自己建立的文件有这些&#xff1a; 新建工程&#xff1a; 从现有的工程文件中将元件添加到原理图库&#xff1a; 元件的摆放&#xff1a; 器件的复制及对齐&#xff1a; 导线、Netlabe、端口的添加&#xff1a; Value值的校对&…

可视化大屏 - 项目1

文章目录 技术栈echarts 可视化需求分析代码实现 技术栈 flexible.js rem 实现不同终端下的响应式布局&#xff0c;根据不同屏幕宽度&#xff0c;自适配布局&#xff1b; html中引入index.js&#xff0c;可以改名为flexible.js&#xff1b;默认划分10份&#xff0c;可以自己修…

HarmonyOS 应用开发之TaskPool和Worker的对比 (TaskPool和Worker)

TaskPool&#xff08;任务池&#xff09;和Worker的作用是为应用程序提供一个多线程的运行环境&#xff0c;用于处理耗时的计算任务或其他密集型任务。可以有效地避免这些任务阻塞主线程&#xff0c;从而最大化系统的利用率&#xff0c;降低整体资源消耗&#xff0c;并提高系统…

日期专题:做题笔记 (时间显示/星期计算/星系炸弹/第几天/纪念日)

目录 时间显示 代码 星期计算 代码 星系炸弹 代码 第几天 纪念日 代码 时间显示 时间显示 这道题主要是单位换算。 ①单位换算 ②输出格式&#xff1a; a. 不足两位补前导零。利用printf输出 b. 注意 long long 输出格式应该是 %lld 长整型 代码 #include <…

Day66-企业级防火墙iptables精讲2

Day66-企业级防火墙iptables精讲2 1. iptables项目案例2&#xff1a;局域网共享上网&#xff1a;2. iptables项目案例3&#xff1a;外网IP的端口映射到内网IP的端口3. 老男孩教育iptables项目案例4&#xff1a;IP一对一映射&#xff08;DMZ&#xff09;4. 老男孩教育iptables项…

Java常用类和基础API

文章目录 1. 字符串相关类之不可变字符序列&#xff1a;String1.1 String的特性1.2 String的内存结构1.2.1 概述1.2.2 练习类型1&#xff1a;拼接1.2.3 练习类型2&#xff1a;new1.2.4 练习类型3&#xff1a;intern() 1.3 String的常用API-11.3.1 构造器1.3.2 字符串对象的比较…

【THM】Protocols and Servers(协议和服务器)-初级渗透测试

介绍 这个房间向用户介绍了一些常用的协议,例如: HTTP协议文件传输协议POP3邮件传输协议IMAP每个协议的每个任务都旨在帮助我们了解底层发生的情况,并且通常被优雅的GUI(图形用户界面)隐藏。我们将使用简单的 Telnet 客户端来使用上述协议进行“对话”,以充分了解GUI客户…

Unity开发一个FPS游戏之三

在前面的两篇博客中&#xff0c;我已实现了一个FPS游戏的大部分功能&#xff0c;包括了第一人称的主角运动控制&#xff0c;武器射击以及敌人的智能行为。这里我将继续完善这个游戏&#xff0c;包括以下几个方面&#xff1a; 增加一个真实的游戏场景&#xff0c;模拟一个废弃的…

5.2 通用代码,数组求和,拷贝数组,si配合di翻转数组

5.2 通用代码&#xff0c;数组求和&#xff0c;拷贝数组&#xff0c;si配合di翻转数组 1. 通用代码 通用代码类似于一个用汇编语言写程序的一个框架&#xff0c;也类似于c语言的头文件编写 assume cs:code,ds:data,ss:stack data segmentdata endsstack segmentstack endsco…

刘小光本就疑心赵本山与他媳妇李琳有染,赵本山为证实清白便想起蛋糕上的字,结果呢?

刘小光本就疑心赵本山与他媳妇李琳有染&#xff0c;赵本山为证实清白便想起蛋糕上的字&#xff0c;结果呢&#xff1f; ——小品《生日快乐》&#xff08;中5&#xff09;的台词 &#xff08;接上&#xff09; 赵本山&#xff1a;噢!对对!那谁&#xff0c;老四&#xff0c;是…

GEE错误——土地分类中出现Line 126:composite.select(...).classify is not a function

错误 Line 126:composite.select(...).classify is not a function 出现 "GEE在土地分类中出现的一个问题... is not a function" 的主要原因可能有几种 1. 变量或函数名拼写错误:检查代码中的该函数或变量名是否正确拼写,包括大小写。 2. 函数或变量未声明:检查…

Docker,anaconda环境的部署与迁移

功能上线将提上日程&#xff0c;但是如何将我windows环境下的程序放到linux服务器的测试环境跑通呢&#xff1f;这是我这整个清明假期将要解决的一件事&#xff0c;最蠢的办法就是看自己的环境下有哪些依赖&#xff0c;如何到服务器上一个一个下&#xff0c;但是首先这个方法很…

Brain.js 的力量:构建多样化的人工智能应用程序

机器学习&#xff08;ML&#xff09;是人工智能 (AI) 的一种形式&#xff0c;旨在构建可以从处理的数据中学习或使用数据更好地执行的系统。人工智能是模仿人类智能的系统或机器的总称。 机器学习&#xff08;ML&#xff09;与复杂的数学纠缠在一起&#xff0c;让大多数初学者…

逻辑代数点

文章目录 与或非与非 或非 与或非异或同或布尔恒等式代入定理例子例子 反演定理例子例子:例子: 真值表 与 逻辑式&#xff1a;逻辑式 与 逻辑图最小项例子:最小项编号最小项性质最小项之和 最大项最大项性质最大项编号 逻辑代数的化简公式化简法卡诺图化简法表示逻辑代数用卡诺…

【蓝桥备赛】异或和——树状数组、DFS

题目链接 异或和 思路分析 树上每个点都有一个点权&#xff0c;对树上的更新操作是修改指定点的点权&#xff0c;查询操作是查询指定点为根结点的子树点权异或和。 这里的这些操作都和树状数组的单点修改和区间查询非常相似&#xff0c;即我们在修改一个点时&#xff0c;同时…

Three.js——scene场景、几何体位置旋转缩放、正射投影相机、透视投影相机

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全干发展 &#x1f4c3;个人状态&#xff1a; 研发工程师&#xff0c;现效力于中国工业软件事业 &#x1f680;人生格言&#xff1a; 积跬步…