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、分布式锁 分布式任务调度...
相机主要调试参数
解析度测试 - 解释如何衡量摄像头捕捉细节的能力,确保图像清晰。锐度评估 - 教你如何判断图像边缘的清晰程度,以优化视觉效果。色散与色彩还原 - 分析色彩准确性,确保所见即所得的色彩一致性。白平衡校正 - 确保在各种光源下拍摄的照片颜色自…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
