CSP-X2024山东小学组T4:刷题
题目链接
CSP-X2024山东小学组T4:刷题
题目描述
比赛之路多艰,做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩,小红就是这样的人。
为了继续提升自己的编程实力,小红整理了一份刷题题单,并选中了题单中的 n n n 道编程题,将它们从 1 1 1 到 n n n 编号,计划用 m m m 天时间按照题目编号顺序做完所有的题目(一道题目只能在同一天完成,不可以使用多天完成同一道题目)。
在小红的计划中,她完成第 i i i 道题目的时间为 a i a_i ai。因为题目有难有易,小红做题时可以找好朋友小明帮忙解题,通过询问小明一道题目的解法,可以省去这个题目的做题时间。当然了,小红做题是为了提升自己,而不是提升小明。因此小红决定一天最多求助小明一次。
本题 m m m 天中,小红做题时间最长一天的总耗时定义为 T T T(小明帮忙做的题目不计入小红的做题总时间)。请你帮小红求出 T T T 的最小值是多少?
输入格式
第一行两个正整数 n n n, m m m,分别表示小红要做的题目数和计划用的天数。
第二行 n n n 个正整数,分别表示每个题目解题所用时间 a i a_i ai。
输出格式
输出仅一行,表示 m m m 天中耗时最长一天的总耗时 T T T 的最小值。
样例 #1
样例输入 #1
4 2
1 2 3 3
样例输出 #1
3
样例 #2
样例输入 #2
3 4
999 999 999
样例输出 #2
0
提示
30% 的数据, n ≤ 1000 n \leq 1000 n≤1000;
60% 的数据, n ≤ 10 , 000 n \leq 10,000 n≤10,000;
100% 的数据, n ≤ 100 , 000 n \leq 100,000 n≤100,000, 0 ≤ a i ≤ 10 , 000 0 \leq a_i \leq 10,000 0≤ai≤10,000, 1 ≤ m ≤ 1000 1 \leq m \leq 1000 1≤m≤1000。
算法思想
根据题目描述,要在 m m m天里按顺序完成 n n n道题,并且每天都可以求助小明帮忙解决一道题,求做题时间最长的一天总耗时 T T T的最小值,显然可以用二分查找来解决。
那么如何判断二分的结果 m i d mid mid是否满足要求呢?这里可以用贪心的思想,在一天中做题时间不超过 m i d mid mid的情况下,尽可能的多做题,不妨设 c n t cnt cnt天能把 n n n道题做完,当 c n t ≤ m cnt\le m cnt≤m时满足要求。
除此之外,对于小明来说,显然要去解决每一天中耗时最长的那道题。
时间复杂度
最坏情况下,在 1 1 1天里把所有题做完,那么最小值 T = n × a i T=n\times a_i T=n×ai,那么时间复杂度为: O ( n × l o g T ) O(n\times logT) O(n×logT)
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100005;
int n, m, a[N];
bool check(LL mid)
{int cnt = 1, maxx = a[1]; //统计每天里耗时最长的题目所用时间LL sum = a[1]; //统计一天里做题的总时间for(int i = 2; i <= n; i ++){maxx = max(maxx, a[i]); //求一天里耗时最长的题目所用时间if(sum + a[i] - maxx <= mid) sum += a[i]; //如果一天的做题时间不超过mid,那么就再做一题else{cnt ++; //需要的天数增加sum = a[i]; maxx = a[i];}}return cnt <= m; //当做完n道题的天数不超过时,满足要求
}
int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> a[i];LL L = 0, R = 1e10; //最坏情况在1天把n道题做完,因此R=n*a[i]while(L < R){LL mid = (L + R) / 2;if(check(mid)) R = mid;else L = mid + 1;}cout << L << endl;
}
相关文章:
CSP-X2024山东小学组T4:刷题
题目链接 CSP-X2024山东小学组T4:刷题 题目描述 比赛之路多艰,做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩,小红就是这样的人。 为了继续提升自己的编程实力,小红整理了一份刷题题单,并选中了题单中的…...
【Windows指令】Windows常用快捷指令
一.查找系统上所有可用的 .cpl 文件 要查找系统上所有可用的 .cpl 文件,你可以浏览到以下目录: C:\Windows\System32在“System32”文件夹中搜索扩展名为 .cpl 的文件,将列出所有可用的控制面板小程序。 ❗某些 .cpl 文件可能仅存在于特定的…...
NLP中的神经网络基础
一:多层感知器模型 1:感知器 解释一下,为什么写成 wxb>0 ,其实原本是 wx > t ,t就是阈值,超过这个阈值fx就为1,现在把t放在左边。 在感知器里面涉及到两个问题: 第一个,特征提…...
安全筑堤,效率破浪 | 统一运维管理平台下的免密登录应用解析
在信息技术迅猛发展的今天,企业运维管理领域正面临着前所未有的复杂挑战。统一运维管理平台作为集中管理和监控IT基础设施的核心工具,其安全性和效率至关重要。免密登录作为一种新兴的身份验证技术,正逐渐成为提升运维管理效率和安全性的重要…...
初学elasticsearch
ES 文章目录 ES一、初识elasticsearch1、什么是elasticsearch,elastic static,Lucene2、倒排索引2.1、正向索引和倒排序索引 3、es与mysql的概念对比3.1、文档3.2、索引3.3、es与数据库中的关系 二、索引库操作1、mapping属性2、创建索引库和映射基本语法…...
HTMLCSS:惊!3D 折叠按钮
这段代码创建了一个具有 3D 效果和动画的按钮,按钮上有 SVG 图标和文本。按钮在鼠标悬停时会显示一个漂浮点动画,图标会消失并显示一个线条动画。这种效果适用于吸引用户注意并提供视觉反馈。按钮的折叠效果和背景渐变增加了页面的美观性。 演示效果 HT…...
SDK 指南
在前端开发中,SDK(Software Development Kit,软件开发工具包)是一个用于帮助开发者在特定平台、框架或技术栈中实现某些功能的工具集。 1. SDK 是什么? SDK 是一种开发工具包,它提供了开发人员实现某些功…...
Web 应用项目开发全流程解析与实战经验分享
目录 一、引言 二、需求分析 三、技术选型 四、架构设计 五、开发实现 六、测试优化 七、部署上线 八、实战经验分享 九、总结 一、引言 在当今数字化时代,Web 应用已经深入到我们生活和工作的各个角落。从社交网络到电子商务,从在线办公到娱乐…...
WPS中插入矩阵的方法
WPS中插入矩阵的方法: 1、先选择插入公式中的矩阵中的第二个括号矩阵 选中矩阵右键,点击插入 点击在此后插入列和在此后插入行,会得到3x3矩阵,如图 分别点击两次会得到4x4矩阵,如图,可以画出4x4矩阵...
Python调用R语言中的程序包来执行回归树、随机森林、条件推断树和条件推断森林算法
要使用Python调用R语言中的程序包来执行回归树、随机森林、条件推断树和条件推断森林算法,重新计算中国居民收入不平等,并进行分类汇总,我们可以使用rpy2库。rpy2允许在Python中嵌入R代码并调用R函数。以下是一个详细的步骤和示例代码&#x…...
uniapp input苹果中文键盘输入拼音直接切换输入焦点监听失效
问题: uniapp微信小程序,苹果手机中文键盘状态下,输入字母时,不点击确定也不点击空白处,直接切换到下一个input输入框,UI界面会保留上个输入框输入的内容,但input、blur事件监听到的值都是空&a…...
多智能体/多机器人网络中的图论法
一、引言 1、网络科学至今受到广泛关注的原因: (1)大量的学科(尤其生物及材料科学)需要对元素间相互作用在多层级系统中所扮演的角色有更深层次的理解; (2)科技的发展促进了综合网…...
华为:数字化转型只有“起点”,没有“终点”
上个月,我收到了一位朋友的私信,他询问我是否有关于华为数字化转型的资料。幸运的是,我手头正好收藏了一些,于是我便分享给他。 然后在昨天,他又再次联系我,并感慨:“如果当初我在进行企业数字…...
centos server系统新装后的网络配置
当前状态: ping www.baidu.com报错 1、检查IP ip addr show记录要编辑的网卡 link/ether 后的XX:XX:XX:XX:XX:XX号 2、以em1为例: vi /etc/sysconfig/network-scripts/ifcfg-em1,新增如下行: HWADDRXX:XX:XX:XX:XX:XX(具体值…...
【问题实录】服务器ping不通win11笔记本
项目场景 测试服务器和win11笔记本之间网络是否通常 问题描述 服务器ping不通win11笔记本,win11笔记本可以ping通服务器 解决方案 1、打开:控制面板\系统和安全\Windows Defender 防火墙 2、点击“高级设置”,然后点击“入站规则”&…...
WEB入门——文件上传漏洞
文件上传漏洞 一、文件上传漏洞 1.1常见的WebShell有哪些?1.2 一句话木马演示1.2 文件上传漏洞可以利用需满足三个条件1.3 文件上传导致的危害 二、常用工具 2.1 搭建upload-labs环境2.2 工具准备 三、文件上传绕过 3.1 客户端绕过 3.1.1 实战练习 :upl…...
公交车信息管理系统:构建智能城市交通的基石
程序设计 本系统主要使用Java语言编码设计功能,MySQL数据库管控数据信息,SSM框架创建系统架构,通过这些关键技术对系统进行详细设计,设计和实现系统相关的功能模块。最后对系统进行测试,这一环节的结果,基本…...
jdk各个版本介绍
JDK(Java Development Kit)是Java开发者用于构建、测试和部署Java应用程序的工具包。随着Java语言的不断演进,JDK也经历了多个版本的更新。下面是对JDK各个主要版本的简要介绍: JDK 1.0 - 1.4(经典时代) •…...
分布式事务解决方案seata和MQ
seata之XA模式 特点:强一致性、会锁定资源。 seata之AT模式 seata之TCC模式 特点:对代码有侵入 MQ解决分布式事务 特点:效率高、实时性差 分布式事务的消息幂等 1、tokenredis保证幂等 2、分布式锁 分布式任务调度...
相机主要调试参数
解析度测试 - 解释如何衡量摄像头捕捉细节的能力,确保图像清晰。锐度评估 - 教你如何判断图像边缘的清晰程度,以优化视觉效果。色散与色彩还原 - 分析色彩准确性,确保所见即所得的色彩一致性。白平衡校正 - 确保在各种光源下拍摄的照片颜色自…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001
qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类,直接把源文件拖进VS的项目里,然后VS卡住十秒,然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分,导致编译的时候找不到了。因…...
JavaScript 标签加载
目录 JavaScript 标签加载script 标签的 async 和 defer 属性,分别代表什么,有什么区别1. 普通 script 标签2. async 属性3. defer 属性4. type"module"5. 各种加载方式的对比6. 使用建议 JavaScript 标签加载 script 标签的 async 和 defer …...
Netty自定义协议解析
目录 自定义协议设计 实现消息解码器 实现消息编码器 自定义消息对象 配置ChannelPipeline Netty提供了强大的编解码器抽象基类,这些基类能够帮助开发者快速实现自定义协议的解析。 自定义协议设计 在实现自定义协议解析之前,需要明确协议的具体格式。例如,一个简单的…...
