蓝桥杯-礼物-二分查找
题目


思路
--刚开始想到暴力尝试的方法,但是N太大了,第一个测试点都超时。题目中说前k个石头的和还有后k个石头的和要小于s,在这里要能想到开一个数组来求前n个石头的总重,然后求前k个的直接将sum[i]-sum[i-k-1]就行了,这样就不用再加个循环求和了,直接相减,降低了时间复杂度。题目中是让求k的,而这个k可以取值的条件与k在数组中的位置有关。可以从1到n/2范围遍历,当然时间复杂度比较大,换用二分查找。二分查找可以遍历每一种可能的k值,并且时间复杂度较小。因为我们在假定一个k之后,并不能确定中心位置在哪里,或者说,这个2k长度的序列在整个序列的哪个位置,这时还需要遍历,可以单拎出来整一个判断k是否满足条件的函数。
--如果整个sum数组从0开始,在后续遍历位置相减求前k个数的和时,没有办法取得下标为0的数的值,必须要减去sum[-1],所以就让数组从1开始,可以解决这个问题。
--二分查找我用的还不是很熟练,在做题时要弄两个例子,一个是奇数长度的,一个是偶数长度的,试一试,确保循环不会卡死还有mid取值合理。
代码
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;long long n, s;
long long sum[1000001]; //表示当前所有石头的重量和。
int k = 0; bool chazhao(int mid){for (long long i = mid; i + mid <= n; i++){if (sum[i] - sum[i - mid] <= s && sum[i + mid] - sum[i] <= s){return true;}}return false;
} //寻找符合条件的mid,这里的mid = k,也就是在寻找合适的k。因为并不确定n的奇偶性。 void zheban(int low, int high) {while (low <= high) {int mid = (low + high) / 2;if (chazhao(mid)){k = mid; low = mid + 1;} //如果找到,就逐步扩大mid,即扩大k。 else{high = mid - 1;} //如果没有找到,就缩小k。 }
}int main(){cin >> n >> s; sum[0] = 0;for (int i = 1; i <= n; i++){int w;cin >> w;sum[i] = w + sum[i - 1];}zheban(1, n); //折半查找k。 cout << k * 2 << endl;return 0;
}
相关文章:
蓝桥杯-礼物-二分查找
题目 思路 --刚开始想到暴力尝试的方法,但是N太大了,第一个测试点都超时。题目中说前k个石头的和还有后k个石头的和要小于s,在这里要能想到开一个数组来求前n个石头的总重,然后求前k个的直接将sum[i]-sum[i-k-1]就行了࿰…...
设计原则、工厂、单例模式
什么是设计模式 简单来说,设计模式就是很多程序员经过相当长的一段时间的代码实践、踩坑所总结出来的一套解决方案,这个解决方案能让我们少写一些屎山代码,能让我们写出来的代码写出来更加优雅,更加可靠。所以设计模式的好处是显而…...
笔记:Mysql 主从搭建
主库 创建用户并授权 create user slave identified with mysql_native_password by 123456 GRANT REPLICATION SLAVE ON *.* to slave%; FLUSH PRIVILEGES;主库配置文件 /etc/my.cnf #日志路径及文件名,目录要是mysql有权限写入 log-bin/var/lib/mysql/binlog …...
HTTP Error 400. The request hostname is invalid.
异常信息 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN""http://www.w3.org/TR/html4/strict.dtd"> <HTML><HEAD><TITLE>Bad Request</TITLE> <META HTTP-EQUIV"Content-Type" Content"text/html;…...
mysql日志( Redo Log 、Undo Log、Bin Log)
InnoDB是一个带有ACID事务支持的存储引擎,其中redo log和undo log是其实现原子性、一致性、隔离性和持久性(ACID)的重要机制。 Redo Log(重做日志) Redo log主要用于实现事务的持久性。它记录了后续可以用来恢复数据…...
HarmonyOS如何创建及调用三方库
介绍 本篇主要向开发者展示了在Stage模型中,如何调用已经上架到三方库中心的社区库和项目内创建的本地库。效果图如下: 相关概念 Navigation:一般作为Page页面的根容器,通过属性设置来展示页面的标题、工具栏、菜单。Tabs&#…...
我手写的轮子开源了
我手写的轮子开源了 文章目录 1.gitee坐标和地址1.1.gitee坐标1.2.gitee地址 2.github坐标和地址2.1.github坐标2.2.github地址 3.总结 1.gitee坐标和地址 1.1.gitee坐标 <dependency><groupId>io.gitee.bigbigfeifei</groupId><artifactId>es-sprin…...
第十九章 linux部署scrapyd
文章目录 1. linux部署python环境1. 部署python源文件环境2. 下载python3. 解压安装包4. 安装5. 配置环境变量6. 检查是否安装成功7. 准备python使用的包8. 安装scrapyd9. 配置scrapyd10. 开放6800端口 2. 部署gerapy1. 本机下载包2. 初始化3. 进入gerapy同步数据库4. 创建用户…...
微信打卡小程序怎么做_用户的每日习惯培养神器
微信打卡小程序:你的每日习惯培养神器 在这个快节奏的现代社会,我们每天都在忙碌中度过,有时候甚至会忘记自己曾经立下的那些小目标、小习惯。然而,随着科技的不断发展,微信打卡小程序的出现,为我们的生活…...
C语言数据在内存中的存储
reference n.提及,谈到;参考,查阅;(引自书或诗歌的)引言,引文; 引文的作者,参考书目;(帮助或意见的)征求,征询;…...
管理公司员工上网行为的软件都有哪些?
随着互联网的飞速发展,企业面临的网络安全威胁也日益加剧。为了保护企业数据安全、提高工作效率,上网行为管理系统及其相关管理软件应运而生。 未来,随着技术的不断进步和网络安全威胁的不断演变,上网行为管理系统及其管理软件将不…...
手撕C语言题典——逆序输出
有这样一个问题:读入一些整数,逆序输出到一行中。已知的是该整数不超过100个。我们该怎么办呢?我们先将这些整数循环输入,输入每个整数之后,我们只能将数组存下来,而这个地方就是数组。 本章可能用到的知识…...
如果保障服务器的安全
如果保障服务器的安全 一、修改它最开始的密码,后期也要一直更换。一般如果有客户来了服务器的话,服务器厂商都会提前把所有的系统都装好,之后再把这个权限交到用户的手里。很多用户可能在这方面不会特别注意,密码也不修改&#x…...
【SQL】1280. 学生们参加各科测试的次数 (笛卡尔积)
前述 知识点回顾:数据库中的四大join & 笛卡尔乘积(以MySQL为例) 笛卡尔积的两种写法 select * from stu,class; select * from stu cross join class; 题目描述 leetcode题目:1280. 学生们参加各科测试的次数 Code 写法…...
高企认定中科技成果转化是什么呢?
其实,这是一个流程,可以用下面的分段进程来表示:企业开展科研立项—科研立项得到科研结果—科研结果用于产品的生产—新产品品质提高带动了销售的增加。 上面的流程,其实是高企审核的核心,不仅仅关系到了量化打分。更…...
第十二届蓝桥杯省赛CC++ 研究生组-货物摆放
还是整数分解问题,注意n本身也是约数 #include <iostream> int main(){printf("2430");return 0; }#include <iostream> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const ll n 2021041820210418LL…...
基于SpringBoot的学生成绩管理系统
基于SpringBootVue的家教管理系统的设计与实现~ 开发语言:Java 数据库:MySQL 技术:SpringBoot 系统功能结构展示 登录界面图 现今,越来越多的人乐于选择一项合适的管理方案,但是普通用户往往受到管理经验地限制&…...
旅游管理系统 |基于springboot框架+ Mysql+Java+Tomcat的旅游管理系统设计与实现(可运行源码+数据库+设计文档)
推荐阅读100套最新项目 最新ssmjava项目文档视频演示可运行源码分享 最新jspjava项目文档视频演示可运行源码分享 最新Spring Boot项目文档视频演示可运行源码分享 目录 前台功能效果图 管理员功能登录前台功能效果图 系统功能设计 数据库E-R图设计 lunwen参考 摘要 研究…...
SpringBoot(整合MyBatis + MyBatis-Plus + MyBatisX插件使用)
文章目录 1.整合MyBatis1.需求分析2.数据库表设计3.数据库环境配置1.新建maven项目2.pom.xml 引入依赖3.application.yml 配置数据源4.Application.java 编写启动类5.测试6.配置类切换druid数据源7.测试数据源是否成功切换 4.Mybatis基础配置1.编写映射表的bean2.MonsterMapper…...
GAMES104-现代游戏引擎 1
主要学习重点还是面向就业,重点复习八股和算法 每天早上八点到九点用来学习这个课程 持续更新中... 第一节 游戏引擎导论 第二节 引擎架构分层 引擎是分层架构的 编辑器功能层资源层核心层平台层 越底层的代码越稳定越坚固,越上层的代码越灵活越开…...
Unity Il2CppDumper原理与实战:解析元数据与二进制对齐
1. 这不是“破解工具”,而是Unity开发者该懂的二进制真相课 你刚在Unity Asset Store下载了一个功能惊艳的插件,却在打包iOS后发现部分逻辑失效;或者接手一个没有源码的旧项目,只有一堆 .dll 和 .so 文件,连主入口…...
DIY复刻经典:Texar Audio Prism动态处理器克隆套件全攻略
1. 项目概述:Texar Audio Prism 克隆套件如果你在专业音频圈子里混过一段时间,尤其是对上世纪八九十年代那些经典的、带点“魔法”色彩的外置动态处理器感兴趣,那么“Texar Audio Prism”这个名字你大概率不会陌生。它不是最常见的1176或者LA…...
小米MIMO最新邀请码
欢迎使用,各得10元体验金...
Onekey终极指南:如何5分钟快速获取Steam游戏清单的免费神器
Onekey终极指南:如何5分钟快速获取Steam游戏清单的免费神器 【免费下载链接】Onekey Onekey Steam Depot Manifest Downloader 项目地址: https://gitcode.com/gh_mirrors/one/Onekey 还在为复杂的Steam游戏清单下载而头疼吗?想要备份游戏资源却不…...
PDF 可视化签名盖章页技术解析
本文是我在设备检测系统项目开发中,无设备检测的技术实现备忘录,记载实现过程。 本文以 PC 端页面 sign-pdf.vue 为主线,说明「无设备报检」在报告审批环节如何通过前后端协作,完成报告/记录 PDF 上的签名、印章、报告编号拖放定位,并在审批通过后由后端合并生成带签章的正…...
C语言(12) 指针的常见操作
指针的常见操作指针变量,有两方面的意思:一个指针指向的内容(数据值,一级)指针变量本身存储的数据 (地址值)#include <stdio.h>int main() {int a 10;int b 0 ;int c 50;int *p NULL;int *q NULL;p &a; // 对指针变量本身进行修改// 对指…...
想深耕网络安全行业,这些必备条件缺一不可
网络空间的攻防对抗日益激烈,网络安全已成为企业生存和国家安全的命脉,它负责构筑数字世界的坚固防线,保护核心资产与用户隐私免受侵害。 想要成为一名优秀的网络安全专家,除了敏锐的安全意识和高度的责任感,更需要锤…...
量子机器学习与傅里叶分析:革新期权定价的混合计算范式
1. 项目概述:当量子机器学习遇见金融定价在金融工程的核心地带,期权定价一直是个计算密集型的硬骨头。传统的蒙特卡洛模拟虽然通用,但为了达到足够的精度,动辄需要百万甚至千万次的路径模拟,计算成本高昂。近年来&…...
ncmdumpGUI终极指南:深度解析网易云音乐NCM加密文件转换技术
ncmdumpGUI终极指南:深度解析网易云音乐NCM加密文件转换技术 【免费下载链接】ncmdumpGUI C#版本网易云音乐ncm文件格式转换,Windows图形界面版本 项目地址: https://gitcode.com/gh_mirrors/nc/ncmdumpGUI ncmdumpGUI是一款专为Windows平台设计…...
告别Appium!用Python+UIAutomator2搞定Android自动化测试(附完整环境搭建与实战代码)
PythonUIAutomator2:Android自动化测试的高效实践指南 在移动应用测试领域,效率与稳定性始终是工程师们追求的核心目标。传统方案如Appium虽然功能全面,但在执行速度和资源消耗方面往往难以满足高频测试需求。本文将带您探索基于Python和UIA…...
