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

【C++题解】1561. 买木头

问题:1561. 买木头

类型:省赛、数组问题、二分答案、贪心、2015江苏省青少年信息学奥林匹克竞赛复赛


题目描述:

有 n 个木材供应商,每个供货商有长度相同一定数量的木头。长木头可以锯短,但短木头不能接长。有一个客人要求 m 根长度相同的木头。要求计算出,此时供货商提供的木头满足客人要求的最长的长度是多少。
例如 n=2,m=30,两个供货商的木头为
12,10 第 1 个供货商的木头长度为 12 ,共有 10 根;
5,10 第 2 个供货商的木头长度为 5 ,共有 10 根。
计算的结果为 5 ,即长度为 12 的木头一根可锯出两根长度为 5 的木头,多余的无用,长度为 5 的木头不动,此时可得到 30 根长度为 5 的木头。

输入:

整数 n,m,L1​,S1​ (1≤n≤10000,1≤m≤1000000,1≤L1​≤10000,1≤S1​≤100)
其中 L1​ 是第一个供货商木头的长,S1​ 是第一个供货商木头数量。其他供货商木头的长度和数量 Li​ 和 Si​(i≥2),由下面的公式给出:
Li​=((Li−1×37011+10193)mod10000)+1
Si​=((Si−1×73011+24793)mod100)+1

输出:

一个整数,即满足要求的 m 根长度相同的木头的最大长度。

样例:

输入:

10 10000 8 20

输出:

201

在这里插入图片描述


完整代码如下:

#include<bits/stdc++.h> 
using namespace std;int m,cmax=0;
vector<int> v;bool cmp(int a,int b){return a>b;
}int findNum(int mid){int c=0,t;for(int i=0;i<v.size();i++){t=v[i];while(t>=mid){++c;t-=mid;}	}return c;
}void myFind(int l,int r){if(l>r){return;}int mid;mid=l+r>>1;if(m>findNum(mid)){return myFind(l,mid-1);}else{cmax=mid;return myFind(mid+1,r);}}
int main(){//一、分析问题//已知:有n个木材供应商。需要m 根长度相同的木头。L 是第一个供货商木头的长,S是第一个供货商木头数量。 //未知:供货商提供的木头满足客人要求的最长的长度是多少。//关系:长木头可以锯短,但短木头不能接长。其他供货商木头的长度和数量 Li 和 Si(i≥2),由下面的公式给出://Li=((Li-1×37011+10193)mod10000)+1//Si=((Si-1×73011+24793)mod100)+1//二、数据定义 int n,li,si;//三、数据输入cin>>n>>m>>li>>si; for(int i=0;i<n;i++){for(int j=0;j<si;j++){v.push_back(li);} li=(li*37011+10193)%10000+1;si=(si*73011+24793)%100+1;}//四、数据计算 sort(v.begin(),v.end(),cmp);myFind(1,v[0]);//五、输出结果 cout<<cmax;return 0;	
}

相关文章:

【C++题解】1561. 买木头

问题&#xff1a;1561. 买木头 类型&#xff1a;省赛、数组问题、二分答案、贪心、2015江苏省青少年信息学奥林匹克竞赛复赛 题目描述&#xff1a; 有 n 个木材供应商&#xff0c;每个供货商有长度相同一定数量的木头。长木头可以锯短&#xff0c;但短木头不能接长。有一个客…...

解决android native包webview,webview中的请求blocked by CORS policy

在stack overflow查&#xff0c;差不多查到的都是些webView.getSettings().setxxx&#xff0c;没用。在github上找别的类似的android native包webview运行pwa的项目&#xff0c;把它们的webView.getSettings().setxxx全搬过来&#xff0c;写了有一页多&#xff0c;一个有用的都…...

链篦机回转窑球团生产工艺

生球在回转窑氧化焙烧&#xff0c;回转窑头部设有燃烧器&#xff0c;燃料可以采用气体、固体、液体。 来自环冷机一冷却段的高温废气作为二次风进入窑内参与燃烧&#xff0c;烧成成品球进入环冷机。 环冷机采用鼓风冷却&#xff0c;热风风箱分为四段&#xff1a; 一段气体引至…...

查看电脑ip地址快捷键是什么?是哪个

在网络世界中&#xff0c;IP地址是每个网络设备的唯一标识&#xff0c;无论是我们的电脑、手机还是其他联网设备&#xff0c;都需要一个独特的IP地址来进行通讯。在日常生活和工作中&#xff0c;我们有时需要查看电脑的IP地址&#xff0c;以便进行网络设置、故障排查或远程连接…...

面试专区|【54道Spring Cloud高频题整理(附答案背诵版)】

什么是Spring Cloud&#xff1f; Spring Cloud是一个基于Spring Boot的开源框架&#xff0c;它提供了在分布式系统中集成各种服务治理功能的工具&#xff0c;如配置管理、服务发现、断路器、智能路由、微代理、控制总线、全局锁、决策竞选、分布式会话和集群状态等。其主要目…...

Shopee(虾皮)怎么获取流量?

店铺流量的高低会直接关联到卖家店铺单量&#xff0c;也关系到一个店铺的营业情况和利润&#xff0c;那么Shopee的流量从哪里来呢&#xff1f; Shopee的平台流量可分为五个部分&#xff1a; 1.自然流量 2.关键字广告流量 3.平台活动流量 4.营销流量 5.粉丝流量 怎么提升…...

Java启动虚拟机默认字符集编码

-Dfile.encodingUTF-8 java程序启动默认字符集编码参数 // 这里会创建一个Charset.defaultCharset().name()的流&#xff0c;在Windows命令行窗口启动&#xff0c;会出现字符编码为GBK的情况 // 导致乱码输入、输出都会有影响 // 解决办法流的读取指定编码new InputStreamRead…...

【单片机编程模式】状态机编程

状态机编程是一种编程模式&#xff0c;它基于有限状态机&#xff08;Finite State Machine&#xff0c;简称FSM&#xff09;的概念。以下是状态机编程的清晰解释&#xff0c;分点表示和归纳&#xff1a; 基本概念&#xff1a; 状态机是一个有向图形&#xff0c;由一组节点&…...

IPSS模块怎么安装到VOS服务器的,到底有没有效果,是不是能大幅度提升VOS3000安全性呢

由于VOS的普及性&#xff0c;不得不承认VOS确实是非常优秀的软交换&#xff0c;但是很多客户在使用过程中都会遇到各种安全问题&#xff0c;比如话费被盗用了&#xff0c;历史话单一堆的非法呼叫话单&#xff0c;严重的影响到了话务安全&#xff0c;并不是那点话费的事了&#…...

C++ STL容器:序列式容器-堆pirority_queue

摘要&#xff1a; CC STL&#xff08;Standard Template Library&#xff0c;标准模板库&#xff09;在C编程中的重要性不容忽视&#xff0c;STL提供了一系列容器、迭代器、算法和函数对象&#xff0c;这些组件极大地提高了C程序的开发效率和代码质量。 STL 容器 分为 2 大类 …...

ECharts在最新版本中使用getInstanceByDom报错处理

引用问题导致报错 如果按如下引用的话&#xff0c;会报错 import echarts from “echarts/lib/echarts”; 原因 在 ECharts 的之前版本中&#xff0c;默认导出了一个名为 echarts 的对象&#xff0c;所以使用 import echarts from “echarts” 是没有问题的。但是在 ECharts …...

利用C语言实现三子棋游戏

文章目录 1.游戏界面2.游戏内容2.1 棋盘类型2.2棋盘的初始化2.3 打印棋盘的界面展示 3.游戏操作3.1 玩家操作3.2 电脑操作3.3 胜负判定 4.代码整合 1.游戏界面 无论写任何程序&#xff0c;我们都需要先去了解它的大概框架&#xff0c;这里我们先把它的初始界面写出来。一个游戏…...

大学教师门诊预约小程序-计算机毕业设计源码73068

摘要 在当今数字化、信息化的浪潮中&#xff0c;大学校园的服务管理正朝着智能化、便捷化的方向迈进。为了优化大学教师的医疗体验&#xff0c;提升门诊预约的效率和便捷性&#xff0c;我们基于Spring Boot框架设计并实现了一款大学教师门诊预约小程序。该小程序不仅提供了传统…...

Python PyCryptodome库介绍与实例

Python PyCryptodome库介绍与实例 1. 安装2. 基本概念3. 使用场景和示例代码3.1 对称加密 - AES3.2 非对称加密 - RSA3.3 哈希函数 - SHA2563.4 消息认证码 - HMAC 4. 总结 PyCryptodome是一个强大的Python加密库,提供了各种加密算法和工具。本文将介绍PyCryptodome的基本概念和…...

《框架封装者 · 自定义初始化事件》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; CSDN入驻不久&#xff0c;希望大家多多支持&#xff0c;后续会继续提升文章质量&#xff0c;绝不滥竽充数…...

ActiViz实战:使用vtkImageClip和vtkImageActor根据滑动条来显示当前图像数据切面

文章目录 一、效果预览二、代码实现三、源码地址一、效果预览 ActiViz实现图像数据切面显示 二、代码实现 public partial class Form1 : Form {private vtkRenderWindowInteractor _interactor;private vtkRenderer _renderer...

【论文笔记】BEVCar: Camera-Radar Fusion for BEV Map and Object Segmentation

原文链接&#xff1a;https://arxiv.org/abs/2403.11761 0. 概述 本文的BEVCar模型是基于环视图像和雷达融合的BEV目标检测和地图分割模型&#xff0c;如图所示。模型的图像分支利用可变形注意力&#xff0c;将图像特征提升到BEV空间中&#xff0c;其中雷达数据用于初始化查询…...

圆通寄15kg30kg一般多少钱?寄大件物品怎么寄最便宜?

作为一名即将毕业的大学生&#xff0c;搬家成了我和室友们共同的难题。尤其是在寄送大件物品时&#xff0c;如何省钱、如何打包、选择哪家快递公司等问题让我们头疼不已。今天&#xff0c;我就来分享一些寄大件物品的省钱技巧以及打包方法&#xff0c;希望对大家有所帮助。 一…...

transformer初探

transformer初探 self-attentionmultihead-attentionencoderdecoder self-attention 其实就是三个矩阵&#xff0c; W q W_q Wq​、 W k W_k Wk​、 W v W_v Wv​&#xff0c;这三个矩阵就是需要训练的参数。分别得到每个token对应的 q q q k k k v v v&#xff0c;其中 q …...

JUC并发编程基础(包含线程概念,状态等具体实现)

一.JUC并发编程基础 1. 并行与并发 1.1 并发: 是在同一实体上的多个事件是在一台处理器上"同时处理多个任务"同一时刻,其实是只有一个事件在发生. 即多个线程抢占同一个资源. 1.2 并行 是在不同实体上的多个事件是在多台处理器上同时处理多个任务同一时刻,大家…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...

GeoServer发布PostgreSQL图层后WFS查询无主键字段

在使用 GeoServer&#xff08;版本 2.22.2&#xff09; 发布 PostgreSQL&#xff08;PostGIS&#xff09;中的表为地图服务时&#xff0c;常常会遇到一个小问题&#xff1a; WFS 查询中&#xff0c;主键字段&#xff08;如 id&#xff09;莫名其妙地消失了&#xff01; 即使你在…...

RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上

一、软件介绍 文末提供程序和源码下载 RushDB 改变了您处理图形数据的方式 — 不需要 Schema&#xff0c;不需要复杂的查询&#xff0c;只需推送数据即可。 二、Key Features ✨ 主要特点 Instant Setup: Be productive in seconds, not days 即时设置 &#xff1a;在几秒钟…...