洛谷 【算法1-6】二分查找与二分答案

【算法1-6】二分查找与二分答案 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

鄙人不才，刷洛谷，迎蓝桥，【算法1-6】二分查找与二分答案 已刷，现将 AC 代码献上，望有助于各位

P2249

【深基13.例1】查找 - 洛谷

题目

解答

思路

使用二分查找的方式解决

代码

#include<iostream>
using namespace std;
const int N = 1000005;
const int M = 100005;
int a[N], find_n[M];
void search(int aim, int l, int r) {
	if (l >= r && a[l] == aim) {
		cout << l + 1 << " ";
		return;
	}
	if (l >= r) {
		cout << "-1 ";
		return;
	}
	int mid = (l + r) / 2;
	if (aim <= a[mid])
		search(aim, l, mid);
	else
		search(aim, mid + 1, r);
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> find_n[i];
	int q = 0;
	while (q < m) {
		search(find_n[q], 0, n - 1);
		q++;
	}
	
	return 0;
}

P1102 A-B 数对

A-B 数对 - 洛谷

题目

解答

思路

在一个数组中，寻找 A-B=C 的数值对 <A, B>，A-B=C 即 A-C=B ，求与 A 对应的 B 的个数

用 map 映射数组元素出现的次数 <value，times>

代码

#include<iostream>
#include<map>
using namespace std;
const int N = 200005;
long long int q[N], C;
map<int, int> a;
long long int n;
int main() {
	cin >> n >> C;
	for (int i = 0; i < n; i++) {
		cin >> q[i];
		a[q[i]]++;
		q[i] -= C;
	}
	long long int ans = 0;
	for (int i = 0; i < n; i++)
		ans += a[q[i]];
	cout << ans;
	return 0;
}

P1873 KEO / 砍树

[COCI 2011/2012 #5] EKO / 砍树 - 洛谷

题目

解答

思路

二分查找 H，0 ≤ H ≤ max_tree

  1. 排序 tree，寻找 max_tree
  2. 二分查找 H，判断条件为 实际伐木总长度 ＜ m

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000005;
int tree[N];
long long int m;
int n;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> tree[i];
	sort(tree, tree + n);
	int l = 0, r = tree[n - 1];
	while (l <= r) {
		int mid =( l + r )/ 2;
		long long sum = 0;
		for (int i = 0; i < n; i++)
			if (tree[i] > mid)
				sum += (tree[i] - mid);
		if (sum < m)
			r = mid - 1;
		else
			l = mid + 1;
	}
	cout << r;
	return 0;
}

P1024 一元三次方程求解

[NOIP2001 提高组] 一元三次方程求解 - 洛谷

题目

解答

思路

浮点数二分

依据上述定理，使用二分算法求根

代码

#include<iostream>
#include<cstdio>
using namespace std;
double a, b, c, d;
double f(double x) {
	return a * x * x * x + b * x * x + c * x + d;
}
int main() {
	cin >> a >> b >> c >> d;
	int s = 0;
	double l, r, mid, f1, f2;
	for (int i = -100; i < 100; i++) {
		l = i;
		r = l + 1;
		f1 = f(l);
		f2 = f(r);
		if (!f1) {
			printf("%.2lf ", l);
			s++;
		}
		if (f1 * f2 < 0) {
			while (r - l > 0.0001) {
				mid = (l + r) / 2;
				if (f(mid) * f(r) <= 0)
					l = mid;
				else
					r = mid;
			}
			printf("%.2lf ", l);
			s++;
		}
		if (s == 3)
			break;
	}
	return 0;
}

P1678 烦恼的高考志愿

烦恼的高考志愿 - 洛谷

题目

解答

思路

先对学校的预计录取分数排序，然后二分查找每个学生最小的不满意度

代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 100005;
const int M = 100005;
int m, n;
long long int student[N], school[M];
int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++)
		cin >> school[i];
	for (int j = 0; j < n; j++)
		cin >> student[j];
	sort(school, school + m);
	long long int ans = 0;
	for (int i = 0; i < n; i++) {//逐个二分
		int l = 0, r = m - 1;
		while (l < r) {
			int mid = (l + r + 1) / 2;
			if (school[mid] <= student[i])
				l = mid;
			else
				r = mid - 1;
		}
		if (student[i] <= school[0])
			ans += (school[0] - student[i]);
		else {
			if (abs(school[l + 1] - student[i]) <= abs(school[l] - student[i]))
				ans += (abs(school[l + 1] - student[i]));
			else
				ans += (abs(school[l] - student[i]));
		}
	}
	cout << ans;
	return 0;
}

P2440 木材加工

木材加工 - 洛谷

题目

解答

思路

二分查找即可

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100005;
int n;
long long int k;
long long int tree[N];
bool check(long long int a) {
	long long int ans = 0;
	for (int i = 0; i < n; i++)
		ans += tree[i] / a;
	if (ans >= k)
		return true;
	else
		return false;
}
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> tree[i];
	sort(tree, tree + n);
	long long int l = 0, r = tree[n - 1];
	long long int mid;
	while (l + 1 < r) {
		//最终l = 114, r = 115，mid = 114, ans = 7
		//l < r, 继续循环 mid = 114，ans = 7, l = 114……无法退出循环
		mid = (l + r) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}
	cout << l;
	return 0;
}

P2678 跳石头

[NOIP2015 提高组] 跳石头 - 洛谷

题目

解答

思路

二分查找最短距离的最大值

检测 mid 是否为最短距离？依次遍历相邻两块石头之间的距离，如果出现比 mid 小的距离，则将此块石头搬走，并记录搬走石头的块数；若搬走石头的块数 > m，则说明 mid 比实际的最小距离短，需要使用 mid 更新左边界；若搬走石头的块数 <= m，则说明 mid 比实际的最小距离长，需要使用 mid 更新右边界

代码

#include<iostream>
using namespace std;
long long int l;
const int N = 50005;
const int M = 50005;
int n, m;
long long int ans;
long long int s[N] = { 0 };
long long int max_m = 0, min_m = 0x3f3f3f3f;
bool check(long long int a) {//检测a是否为最短距离
	int count = 0;//count记录拿去石头的块数
	int front = 0;//front表示前一块石头
	for (int i = 1; i <= n + 1; i++) {
		if (s[i] - s[front] < a)//若两块石头之间的距离小于目前的最小距离，则将这块石头拿掉
			count++;
		else
			front = i;
	}
	if (count > m)
		return false;
	else
		return true;
}
int main() {
	cin >> l >> n >> m;
	max_m = l;
	if (m == 0 && n == 0) {//只有起点和终点，中间没有石头的情况
		cout << l;
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		long long int t = s[i] - s[i - 1];
		if (t < min_m)
			min_m = t;
	}
	s[n + 1] = l;
	if ((s[n + 1] - s[n]) < min_m)
		min_m = s[n - 1] - s[n];
	long long int mid;
	while (min_m <= max_m) {//不能去掉等号，否则少循环一次
		mid = (min_m + max_m) / 2;
		if (check(mid)) {
			ans = mid;
			min_m = mid + 1;//需要搬去的石头数<=m，说明现在的最短距离偏短，需要更大，更新最小边界
		}
		else
			max_m = mid - 1;//需要搬去的石头数>m，说明现在的最短距离>实际的最短距离，需要更小，更新最大边界
	}
	cout << ans;
	return 0;
}

P3853 路标设置

[TJOI2007] 路标设置 - 洛谷

题目

解答

思路

二分查找最长距离的最小值

检测 mid 是否为最长距离？依次遍历相邻两个路障之间的距离，如果出现比 mid 大的距离，则设置新的路障，并记录设置的路障的数量；若新设置的路障数 > k，则说明 mid 比实际的最长距离短，需要使用 mid 更新左边界；若新设置的路障数 <= k，则说明 mid 比实际的最长距离长，需要使用 mid 更新右边界

代码

代码

#include<iostream>
using namespace std;
long long int l;
const int N = 100005;
int k, n;
long long int s[N];
long long int ans;
bool check(long long int mid) {//检测mid是否为最大距离
	int y = k;
	int qian = 0;
	for (int i = 1; i < n; i++) {//遍历原路障，判断此路障与前一个路障直接是否需要安装新的路障
		if (y < 0)
			break;
		if ((s[i] - qian) <= mid)//此路障与前一个路障之间的距离<最大距离，继续遍历
			qian = s[i];
		else {//此路障与前一个路障之间的距离>最大距离，安装路障，新安装的路障与原前一个路障之间的距离为mid
			qian = qian + mid;
			i--;//安装路障之后，不能直接判断原来的下一个路障，还得在此基础上，再次判断此处是否需要再次安装路障
			y--;
		}
	}
	if (y >= 0)
		return true;
	return false;
}
int main() {
	cin >> l >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> s[i];
	long long int min_m = 0, max_m = l;
	while (min_m <= max_m) {
		long long int mid = min_m + (max_m - min_m) / 2;
		if (check(mid)) {
			ans = mid;
			max_m = mid - 1;//需要新设的路障<=k,说明现在的最长距离偏长，需要更短，更新最大边界
		}
		else
			min_m = mid + 1;//需要新设的路障>k,说明现在的最长距离偏短，需要更长，更新最小边界
	}
	cout << ans << endl;
	return 0;
}

P1182 数列分段 SectionⅡ

数列分段 Section II - 洛谷

题目

解答

思路

二分查找子序列和最大值的最小值

检测 mid 是否为子序列和的最大值？依次遍历数组元素，如果出现子序列和 >mid，则将当前元素作为新的子序列的第一个元素；若段数 >= m，则说明 mid 比实际的最大子序列和小，需要使用 mid 更新左边界；若段数 < m，则说明 mid 比实际的最大子序列和大，需要使用 mid 更新右边界

代码

#include<iostream>
using namespace std;
const int N = 100005;
int n, m;
long long int num[N], l = 0, r = 0x3f3f3f3f;
long long int ans;
bool check(long long int mid) {
	int cnt = 0, s = 0;
	for (int i = 0; i < n; i++) {
		if ((s + num[i]) <= mid)
			s += num[i];
		else {
			s = num[i];
			cnt++;
		}
	}
	return cnt >= m;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
		if (l < num[i])
			l = num[i];
		r += num[i];
	}
	while (l <= r) {
		long long int mid = (l + r) / 2;
		if (check(mid))
			l = mid + 1;//实际划分的组数>=要求的组数，说明子序列和偏小，实际子序列和应该更大
		else
			r = mid - 1;//实际划分的组数<要求的组数，说明子序列和偏大，实际子序列和应该更小
	}
	cout << l;
	return 0;
}

P1163 银行贷款

银行贷款 - 洛谷

题目

解答

思路

二分查找月利率，查找的范围大一些，要包含所有的范围

遍历每一个月，每月先计算利息，再还款

还款结束后，若欠债为0，或二分查找范围小于 0.0001 时，表示已经找到月利率；

若存在欠债，说明月利率太大了，使得利息过多

若不存在欠债，且多还款了，说明月利率太小了，使得利息过少

代码

#include<iostream>
using namespace std;
double w_s, w;
double year;
double lx = 0;
double find(double l, double r) {
	double mid = (l + r) / 2;
	double qianzai = w_s;//表示目前的欠债
	for (int i = 0; i < year; i++) 
		qianzai = qianzai * (1 + mid) - w;
	if (qianzai == 0 || r - l < 0.0001)
		return mid;
	if (qianzai < 0)
		return find(mid, r);
	else
		return find(l, mid);
}
int main() {
	cin >> w_s >> w >> year;
	double h = find(0, 5);//二分，开大一点，保证所有数都可以通过
	printf("%.1lf", h * 100);
	return 0;
}

P3743 kotori 的设备

kotori的设备 - 洛谷

题目

解答

思路

二分查找设备使用时间

特判：用电量<=充电量，可以无限使用

如何查找设备最久使用时间？检测需要的充电量与实际充电量的关系，若需要的充电量<=实际充电量，说明设备使用时间<最久设备使用时间，更新二分的左边界；反之，说明设备使用时间>最久设备使用时间，更新二分的右边界

代码

#include<iostream>
using namespace std;
const int N = 100005;
double p;
int n;
double a[N], b[N];
double sum = 0;//需要的能量
bool check(double mid) {
	double max = p * mid;//max表示充电器最多提供的能力
	sum = 0;
	for (int i = 0; i < n; i++) {//遍历每一台设备
		if ((a[i] * mid) <= b[i])//设备已有的能量>需要的能量
			continue;
		sum = sum + ((a[i] * mid) - b[i]);//计算充电量
	}
	return sum <= max;
}
int main() {
	cin >> n >> p;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		sum += a[i];
	}
	//特判：无限使用
	if (sum <= p) {
		cout << "-1" << endl;
		return 0;
	}
	double l = 0, r = 1e10;
	while ((r - l) > 0.0001) {
		double mid = (l + r) / 2;
		if (check(mid))//需要的充电量<=实际充电量
			l = mid;
		else
			r = mid;
	}
	cout << l << endl;
	return 0;
}

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

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

相关文章

开发分销商城小程序助力您的业务快速增长

开发分销商城小程序助力您的业务快速增长

一、什么是分销商城小程序&#xff1f; 分销商城小程序是一种基于微信平台开发的小程序&#xff0c;可以帮助商家快速建立自己的分销体系&#xff0c;实现商品的快速销售。 二、分销商城小程序的优势&#xff1a; 低成本&#xff1a;开发成本低&#xff0c;无需投入大量资金…
阅读更多...
架构设计：数据库扩展

架构设计：数据库扩展

引言 随着业务的发展和用户规模的增长&#xff0c;数据库往往会面临着存储容量不足、性能瓶颈等问题。为了解决这些问题&#xff0c;数据库扩展成为了一种常见的解决方案。在数据库扩展的实践中&#xff0c;有许多不同的策略和技术可供选择&#xff0c;其中包括水平拆分、垂直…
阅读更多...
【干货】12个开源免费的程序员简历模板

【干货】12个开源免费的程序员简历模板

前言 昨天有小伙伴在技术群里问有没有开源的程序员简历模板&#xff0c;其实很早之前在DotNetGuide中已经有整理过&#xff0c;只是一直没有写文章推广过&#xff0c;由此有了今天这篇文章&#xff0c;假如大家有更好的免费简历模板资源欢迎大家在文章评论区留言✌。 公众号回…
阅读更多...
Jenkins使用遇到的一些问题

Jenkins使用遇到的一些问题

一&#xff1a;插件依赖报错 比如遇到一堆插件报错&#xff0c;不是提示版本对不上&#xff0c;就是启用不了 这样直接把Jenkins升级就行了&#xff0c;比如我这个是命令行启动的&#xff0c;直接把他替换就好了 如果是遇到插件依赖报错&#xff0c;比如A插件异常 则点击这个插…
阅读更多...
冒泡排序改进方案

冒泡排序改进方案

冒泡排序 BubbleSort 冒泡排序是一种比较简单的 稳定排序 算法&#xff0c;效率不高&#xff0c;因此实际当中用到的机会并不多。但 作为快速排序算法的基础&#xff0c;还是有必要了解一下。 顾名思义&#xff0c;冒泡就是指大的数字&#xff08;气泡&#xff09;会优先从底部…
阅读更多...
Java毕业设计-基于jsp+servlet的图书管理系统-第66期

Java毕业设计-基于jsp+servlet的图书管理系统-第66期

获取源码资料&#xff0c;请移步从戎源码网&#xff1a;从戎源码网_专业的计算机毕业设计网站 项目介绍 基于jspservlet的图书管理系统&#xff1a;前端jsp、jquery&#xff0c;后端 servlet、jdbc&#xff0c;集成图书管理、图书分类管理、图书借阅、图书归还、公告、读者等…
阅读更多...
linux前端部署

linux前端部署

安装jdk 配置环境变量 刷新配置文件 source profile source /etc/profile tomcat 解压文件 进去文件启动tomcat 开放tomcat的端口号 访问 curl localhsot:8080 改配置文件 改IP,改数据库名字&#xff0c;密码&#xff0c; 安装数据库 将war包拖进去 访问http:…
阅读更多...
软件版本号解读（语义化SemVer、日历化CalVer及标识符）

软件版本号解读（语义化SemVer、日历化CalVer及标识符）

1. 版本控制规范 1.1. 语义化版本&#xff08;SemVer&#xff09; 版本格式&#xff1a;主版本号.次版本号.修订号&#xff0c;版本号递增规则&#xff1a; 主版本号(MAJOR version)&#xff1a;添加了不兼容的 API 修改&#xff0c;次版本号(MINOR version)&#xff1a;添加…
阅读更多...
多维时序 | Matlab实现CPO-BiTCN-BiGRU冠豪猪优化时间卷积神经网络双向门控循环单元多变量时间序列预测模型

多维时序 | Matlab实现CPO-BiTCN-BiGRU冠豪猪优化时间卷积神经网络双向门控循环单元多变量时间序列预测模型

多维时序 | Matlab实现CPO-BiTCN-BiGRU冠豪猪优化时间卷积神经网络双向门控循环单元多变量时间序列预测模型 目录 多维时序 | Matlab实现CPO-BiTCN-BiGRU冠豪猪优化时间卷积神经网络双向门控循环单元多变量时间序列预测模型预测效果基本介绍程序设计参考资料 预测效果 基本介绍…
阅读更多...
XUbuntu22.04之解决：systemd-journald占用cpu过高问题(二百一十三)

XUbuntu22.04之解决：systemd-journald占用cpu过高问题(二百一十三)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…
阅读更多...
具有准电阻负载阻抗的带宽增强型 Doherty 功率放大器(2023.05 MTT)--从理论到ADS版图

具有准电阻负载阻抗的带宽增强型 Doherty 功率放大器(2023.05 MTT)--从理论到ADS版图

具有准电阻负载阻抗的带宽增强型 Doherty 功率放大器(2023.05 MTT)–从理论到ADS版图 原文: Bandwidth-Enhanced Doherty Power Amplifier With Optimized Quasi-Resistive Power-Combing Load Impedance 发表于APRIL 2023&#xff0c;在微波顶刊IEEE T MTT上面&#xff0c;使…
阅读更多...
第十四章[面向对象]:14.9:定制类

第十四章[面向对象]:14.9:定制类

一，__len__()方法返回长度 1,len()函数 len()函数: 功能:len() 函数返回对象（字符、列表、元组等）长度或项目个数 语法: len( s ) 参数:s : 要查询长度的对象 返回值: 返回对象长度 2,没有定义__len__()方法时，对实例应用len()函数会引发TypeError class Student: …
阅读更多...
【Spring】声明式事务 spring-tx

【Spring】声明式事务 spring-tx

文章目录 声明式事务是什么&#xff1f;一、Spring事务管理器二、基于注解的声明式事务1.1 准备工作1.2 基本事务控制1.3 事务属性&#xff1a;只读1.4 事务属性&#xff1a;超时时间1.5 事务属性&#xff1a;事务异常1.6 事务属性&#xff1a;事务隔离级别1.7 事务属性&#x…
阅读更多...
xff注入 [CISCN2019 华东南赛区]Web111

xff注入 [CISCN2019 华东南赛区]Web111

打开题目 看见smarty 想到模板注入 又看见ip 想到xff注入 一般情况下输入{$smarty.version}就可以看到返回的smarty的版本号。该题目的Smarty版本是3.1.30 在Smarty3的官方手册里有以下描述: Smarty已经废弃{php}标签&#xff0c;强烈建议不要使用。在Smarty 3.1&#xff…
阅读更多...
springsecurity+vue前后端分离适配cas认证的跨域问题

springsecurity+vue前后端分离适配cas认证的跨域问题

0. cas服务搭建参考:CAS 5.3服务器搭建_cas-overlay-CSDN博客 1. 参照springsecurity适配cas的方式, 一直失败, 无奈关闭springssecurity认证 2. 后端服务适配cas: 参考前后端分离项目(springbootvue)接入单点登录cas_前后端分离做cas单点登录-CSDN博客 1) 引入maven依赖 …
阅读更多...
css实现悬浮卡片

css实现悬浮卡片

结果展示 html代码 <!doctype html> <html lang"zh"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge,chrome1"> <meta name"viewport" content"…
阅读更多...
MATLAB中的稀疏矩阵和密集矩阵

MATLAB中的稀疏矩阵和密集矩阵

在MATLAB中&#xff0c;矩阵可以表示为密集或稀疏格式。通常&#xff0c;矩阵默认以密集格式存储&#xff0c;这意味着每个元素都明确地存储在内存中&#xff0c;无论它的值是多少。然而&#xff0c;当矩阵含有大量的零元素时&#xff0c;这种存储方式就会变得非常低效。为了更…
阅读更多...
【深度学习目标检测】十八、基于深度学习的人脸检测系统-含GUI和源码（python，yolov8）

【深度学习目标检测】十八、基于深度学习的人脸检测系统-含GUI和源码（python，yolov8）

人脸检测是计算机视觉中的一个重要方向&#xff0c;也是一个和人们生活息息相关的研究方向&#xff0c;因为人脸是人最重要的外貌特征。人脸检测技术的重要性主要体现在以下几个方面&#xff1a; 人脸识别与安全&#xff1a;人脸检测是人脸识别系统的一个关键部分&#xff0c;是…
阅读更多...
【QT QML】软件打包，生成安装包

【QT QML】软件打包，生成安装包

一、版本 Desktop 5.15.2 MinGW 64-bit二、打包 1. 编译Release版本 2. 在工程目录下找到Realse文件夹 3. 拷贝文件 ***-Desktop_Qt_5_15_2_MinGW_64_bit-Release - release - xxx.exe到一个新文件夹中 4. 开启相应打包工具&#xff08;根据自己的编译器和版本选择&#xff0…
阅读更多...
PPT大珩助手使用方法的详细介绍

PPT大珩助手使用方法的详细介绍

软件介绍 PPT大珩助手是一款全新设计的Office PPT插件&#xff0c;它是一款功能强大且实用的PPT辅助工具&#xff0c;支持Wps Word和Office Word&#xff0c;能够轻松帮助您修改、优化和管理幻灯片。凭借丰富的功能和用户友好的界面&#xff0c;PPT大珩助手能够助力您打造出精…
阅读更多...
最新文章

Copyright @ 2022~2023