当前位置: 首页 > 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 并行 是在不同实体上的多个事件是在多台处理器上同时处理多个任务同一时刻,大家…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...