当前位置: 首页 > news >正文

蓝桥杯-礼物-二分查找

题目

思路

--刚开始想到暴力尝试的方法,但是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;
}

相关文章:

蓝桥杯-礼物-二分查找

题目 思路 --刚开始想到暴力尝试的方法&#xff0c;但是N太大了&#xff0c;第一个测试点都超时。题目中说前k个石头的和还有后k个石头的和要小于s&#xff0c;在这里要能想到开一个数组来求前n个石头的总重&#xff0c;然后求前k个的直接将sum[i]-sum[i-k-1]就行了&#xff0…...

设计原则、工厂、单例模式

什么是设计模式 简单来说&#xff0c;设计模式就是很多程序员经过相当长的一段时间的代码实践、踩坑所总结出来的一套解决方案&#xff0c;这个解决方案能让我们少写一些屎山代码&#xff0c;能让我们写出来的代码写出来更加优雅&#xff0c;更加可靠。所以设计模式的好处是显而…...

笔记:Mysql 主从搭建

主库 创建用户并授权 create user slave identified with mysql_native_password by 123456 GRANT REPLICATION SLAVE ON *.* to slave%; FLUSH PRIVILEGES;主库配置文件 /etc/my.cnf #日志路径及文件名&#xff0c;目录要是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事务支持的存储引擎&#xff0c;其中redo log和undo log是其实现原子性、一致性、隔离性和持久性&#xff08;ACID&#xff09;的重要机制。 Redo Log&#xff08;重做日志&#xff09; Redo log主要用于实现事务的持久性。它记录了后续可以用来恢复数据…...

HarmonyOS如何创建及调用三方库

介绍 本篇主要向开发者展示了在Stage模型中&#xff0c;如何调用已经上架到三方库中心的社区库和项目内创建的本地库。效果图如下&#xff1a; 相关概念 Navigation&#xff1a;一般作为Page页面的根容器&#xff0c;通过属性设置来展示页面的标题、工具栏、菜单。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. 创建用户…...

微信打卡小程序怎么做_用户的每日习惯培养神器

微信打卡小程序&#xff1a;你的每日习惯培养神器 在这个快节奏的现代社会&#xff0c;我们每天都在忙碌中度过&#xff0c;有时候甚至会忘记自己曾经立下的那些小目标、小习惯。然而&#xff0c;随着科技的不断发展&#xff0c;微信打卡小程序的出现&#xff0c;为我们的生活…...

C语言数据在内存中的存储

reference n.提及&#xff0c;谈到&#xff1b;参考&#xff0c;查阅&#xff1b;&#xff08;引自书或诗歌的&#xff09;引言&#xff0c;引文&#xff1b; 引文的作者&#xff0c;参考书目&#xff1b;&#xff08;帮助或意见的&#xff09;征求&#xff0c;征询&#xff1b…...

管理公司员工上网行为的软件都有哪些?

随着互联网的飞速发展&#xff0c;企业面临的网络安全威胁也日益加剧。为了保护企业数据安全、提高工作效率&#xff0c;上网行为管理系统及其相关管理软件应运而生。 未来&#xff0c;随着技术的不断进步和网络安全威胁的不断演变&#xff0c;上网行为管理系统及其管理软件将不…...

手撕C语言题典——逆序输出

有这样一个问题&#xff1a;读入一些整数&#xff0c;逆序输出到一行中。已知的是该整数不超过100个。我们该怎么办呢&#xff1f;我们先将这些整数循环输入&#xff0c;输入每个整数之后&#xff0c;我们只能将数组存下来&#xff0c;而这个地方就是数组。 本章可能用到的知识…...

如果保障服务器的安全

如果保障服务器的安全 一、修改它最开始的密码&#xff0c;后期也要一直更换。一般如果有客户来了服务器的话&#xff0c;服务器厂商都会提前把所有的系统都装好&#xff0c;之后再把这个权限交到用户的手里。很多用户可能在这方面不会特别注意&#xff0c;密码也不修改&#x…...

【SQL】1280. 学生们参加各科测试的次数 (笛卡尔积)

前述 知识点回顾&#xff1a;数据库中的四大join & 笛卡尔乘积&#xff08;以MySQL为例&#xff09; 笛卡尔积的两种写法 select * from stu,class; select * from stu cross join class; 题目描述 leetcode题目&#xff1a;1280. 学生们参加各科测试的次数 Code 写法…...

高企认定中科技成果转化是什么呢?

其实&#xff0c;这是一个流程&#xff0c;可以用下面的分段进程来表示&#xff1a;企业开展科研立项—科研立项得到科研结果—科研结果用于产品的生产—新产品品质提高带动了销售的增加。 上面的流程&#xff0c;其实是高企审核的核心&#xff0c;不仅仅关系到了量化打分。更…...

第十二届蓝桥杯省赛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的家教管理系统的设计与实现~ 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 系统功能结构展示 登录界面图 现今&#xff0c;越来越多的人乐于选择一项合适的管理方案&#xff0c;但是普通用户往往受到管理经验地限制&…...

旅游管理系统 |基于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

主要学习重点还是面向就业&#xff0c;重点复习八股和算法 每天早上八点到九点用来学习这个课程 持续更新中... 第一节 游戏引擎导论 第二节 引擎架构分层 引擎是分层架构的 编辑器功能层资源层核心层平台层 越底层的代码越稳定越坚固&#xff0c;越上层的代码越灵活越开…...

Topit:macOS窗口置顶神器,让多任务处理效率翻倍

Topit&#xff1a;macOS窗口置顶神器&#xff0c;让多任务处理效率翻倍 【免费下载链接】Topit Pin any window to the top of your screen / 在Mac上将你的任何窗口强制置顶 项目地址: https://gitcode.com/gh_mirrors/to/Topit 你是否经常在macOS上同时处理多个任务时…...

STM32单片机学习(28) —— STM32的SPI外设

文章目录概述SPI通信的移位机制&#xff08;以bit为单位&#xff09;SPI外设框图第一部分&#xff1a;数据通路SPI通信的数据帧格式SPI外设移位机制&#xff08;以字节为单位&#xff09;第二部分&#xff1a;主机时钟生成器SPI通信时钟频率与传输速率第三部分&#xff1a;主从…...

手把手教你为WCH CH582移植CherryUSB主机栈(基于RT-Thread,含中断优化)

基于RT-Thread的WCH CH582 USB主机协议栈深度移植指南在嵌入式开发领域&#xff0c;USB主机功能的实现往往意味着设备能够直接连接各类USB外设&#xff0c;从简单的键盘鼠标到复杂的存储设备。对于使用WCH CH582这类RISC-V内核MCU的开发者而言&#xff0c;原厂SDK提供的USB主机…...

光效崩坏?噪点泛滥?色温漂移?——Midjourney专业级光效渲染全流程校准协议,含ACEScg色彩空间适配模板

更多请点击&#xff1a; https://kaifayun.com 第一章&#xff1a;光效崩坏、噪点泛滥与色温漂移的系统性归因诊断 图像采集链路中出现的光效崩坏、噪点泛滥与色温漂移并非孤立现象&#xff0c;而是光学设计、传感器响应、ISP管线调度及环境耦合失配共同作用的结果。三者常呈现…...

Web渗透测试能力成长地图:从工具使用到漏洞认知跃迁

1. 这不是工具清单&#xff0c;而是一张Web渗透测试的“能力成长地图”你刚点开这篇文章&#xff0c;大概率正站在两个路口之间&#xff1a;一边是网上铺天盖地的“十大免费扫描器推荐”&#xff0c;点进去全是截图下载链接一句“一键扫漏洞”&#xff0c;结果装完跑两下&#…...

百度文心一言开发者如何通过Taotoken低成本接入多模型API

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 百度文心一言开发者如何通过Taotoken低成本接入多模型API 对于已经熟悉并正在使用百度文心一言等国产大模型API的开发者而言&#…...

C++ vector容器总结

vector基本概念功能&#xff1a;vector数据结构和数组非常相似&#xff0c;也称为单端数组vector与普通数组区别&#xff1a;不同之处在于数组是静态空间&#xff0c;而vector可以动态扩展动态扩展&#xff1a;并不是在原空间之后续接新空间&#xff0c;而是找更大的内存空间&a…...

Claude SWOT分析(内部风控文档流出版):3类高危使用场景+2个监管红线预警

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Claude SWOT分析&#xff08;内部风控文档流出版&#xff09;&#xff1a;3类高危使用场景2个监管红线预警 高危使用场景识别 在企业级AI应用中&#xff0c;Claude模型若未经严格风控适配&#xff0c;…...

Hitboxer:终极SOCD按键重映射解决方案,彻底解决游戏按键冲突问题

Hitboxer&#xff1a;终极SOCD按键重映射解决方案&#xff0c;彻底解决游戏按键冲突问题 【免费下载链接】socd Key remapper for epic gamers 项目地址: https://gitcode.com/gh_mirrors/so/socd 在激烈的游戏对战中&#xff0c;你是否曾因同时按下左右方向键而导致角色…...

仅限首批200位架构师获取:DeepSeek-DDD联合建模工作坊实录(含领域事件风暴原始会议录像+决策日志)

更多请点击&#xff1a; https://kaifayun.com 第一章&#xff1a;DeepSeek领域驱动设计的范式演进与本质洞察 DeepSeek作为面向大规模智能体协同与复杂业务语义建模的新一代AI原生架构&#xff0c;其领域驱动设计&#xff08;DDD&#xff09;实践已突破传统分层单体范式&…...