信奥赛CSP-J复赛集训(数学思维专题)(11):P9585 「MXOI Round 2」酒店
信奥赛CSP-J复赛集训(数学思维专题)(11):P9585 「MXOI Round 2」酒店
题目描述
小 C 开了一家酒店,叫做 CC Hotel。
一天,CC Hotel 来了 n n n 位客人。小 C 需要把他们都安排在酒店的某一层中。每个房间中只能安排一位客人。
这一层共有 m m m 间房间,这 m m m 间房间都是空的,且这 m m m 间房间形成了一个环形,即对于所有的 1 ≤ x ≤ m 1 \le x \le m 1≤x≤m,都有第 x x x 间房间与第 ( ( x m o d m ) + 1 ) ((x \bmod m)+1) ((xmodm)+1) 间房间相邻,第 ( ( x m o d m ) + 1 ) ((x \bmod m)+1) ((xmodm)+1) 间房间与第 x x x 间房间相邻,其中 x m o d m x \bmod m xmodm 表示 x x x 除以 m m m 得到的余数。
这 n n n 位客人都十分挑剔,他们希望与自己的房间相邻的房间中没有人。对于某一位客人,若与他的房间相邻的房间中,有 k k k 间房间有人,则这位客人会产生 k k k 点愤怒值。
你需要帮助小 C 安排房间,使得所有客人的愤怒值之和最小,并输出所有客人的愤怒值之和的最小值。
输入格式
两个整数 n , m n,m n,m。
输出格式
一个整数,表示所有客人的愤怒值之和的最小值。
输入输出样例 #1
输入 #1
3 5
输出 #1
2
输入输出样例 #2
输入 #2
1 4
输出 #2
0
说明/提示
【样例解释 #1】
对于这 5 5 5 间房间,其中一组满足条件的安排方案为:不住人、住人、住人、不住人、住人。
可以证明所有客人的愤怒值之和的最小值为 2 2 2。
【数据范围】
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100, 3 ≤ m ≤ 100 3 \le m \le 100 3≤m≤100,保证 n ≤ m n \le m n≤m。
测试点编号 | 特殊性质 |
---|---|
1 ∼ 3 1\sim3 1∼3 | 保证 2 n ≤ m 2n\le m 2n≤m |
4 ∼ 6 4\sim6 4∼6 | 保证 m = n + 1 m=n+1 m=n+1 |
7 ∼ 10 7\sim10 7∼10 | 无 |
AC代码:
#include <bits/stdc++.h>
using namespace std;
int n, m, ans;int main() {cin >> n >> m;// 当房间数足够多时,可以完全隔离所有客人,总愤怒值为0if (m >= 2 * n) {ans = 0;} else {if (m % 2 == 0) {// 当房间数为偶数时,每多安排一个客人超过m/2,总愤怒值增加4ans = (n - m / 2) * 4;} else {// 当房间数为奇数时,第一个多出的客人增加2,之后每个增加4ans = 2 + (n - m / 2 - 1) * 4;}}cout << ans;return 0;
}
功能分析
- 输入处理:读取客人数量
n
和房间数量m
。 - 完全隔离情况:当房间数
m
足够大(m >= 2n
)时,所有客人可以隔开入住,此时总愤怒值为0。 - 偶数房间处理:若房间数
m
是偶数,最多可无冲突安排m/2
位客人。超出部分每位客人导致总愤怒值增加4。 - 奇数房间处理:若房间数
m
是奇数,第一个超出m/2
的客人导致总愤怒值增加2,后续每位增加4。 - 输出结果:计算并输出所有客人愤怒值的最小总和。
该算法通过数学推导找到最优安排策略,时间复杂度为O(1),高效解决了问题。
文末彩蛋:
点击查看老师的个人主页,学习csp信奥赛完整系列课程:
https://edu.csdn.net/lecturer/7901
相关文章:
信奥赛CSP-J复赛集训(数学思维专题)(11):P9585 「MXOI Round 2」酒店
信奥赛CSP-J复赛集训(数学思维专题)(11):P9585 「MXOI Round 2」酒店 题目描述 小 C 开了一家酒店,叫做 CC Hotel。 一天,CC Hotel 来了 n n n 位客人。小 C 需要把他们都安排在酒店的某一层…...
python: audioFlux XXCC 提取梅尔频率倒谱系数 MFCC
承上一篇:python:audioFlux 使用教程 XXCC: 倒谱系数,支持所有频谱类型. 可以提取梅尔频率倒谱系数(MFCC) Cepstrum coefficients, supports all spectrum types. 以下是使用 audioflux 库中 XXCC 类计算倒谱系数…...
PHP + Go 如何协同打造高并发微服务?
为什么需要 PHP Go 协同? 在微服务架构中,PHP 和 Go 看似是“两个世界”的语言,但它们的互补性极强: PHP:开发效率高、生态成熟,适合快速实现复杂业务逻辑(如电商订单、用户系统)…...
k8s工具使用
Kubectl Cheat Sheet k8s的命令级别 1.基础命令(初级) 2.基础命令(中级) 3.部署命令 4.集群管理命令 5.故障排查和调试命令 6.高级命令 7.设置命令 8.其它命令 命令行提示 为了使用kubectl命令更加高效,我们可以选择安装一下开源软件来增加操作kubectl命令的快捷方式,同…...
uml制做参考-以代码画UML图
【PlantUML系列】类图(一)_plantuml skin-CSDN博客 UML入门以及Plant UML工具介绍_plantuml-CSDN博客 UML类图详解-CSDN博客 【PlantUML】-类图-CSDN博客 【掌握绘图艺术】用PlantUML绘制完美UML图表,编程开发者的福音 - 知乎 如何优化P…...
深入解析B站androidApp接口:从bilibili.api.ticket.v1.Ticket/GetTicket到SendMsg的技术分析
前言 最近一段时间,我对B站的App接口进行了深入分析,特别是关注了认证机制和私信功能的实现。通过逆向工程和网络抓包,发现了B站移动端API的底层工作原理,包括设备标识生成机制、认证流程和消息传输协议。本文将分享这些研究成果…...
[AI ][Dify] 构建一个自动化新闻编辑助手:Dify 工作流实战指南
在内容创作行业中,自动化辅助工具已成为提升编辑效率的重要利器。本文将通过 Dify 平台,演示如何构建一个**“新闻编辑助手”**,实现从网页抓取、文本翻译、标题生成,到新闻配图的全流程自动化。 🎯 目标概览 这个工作流旨在实现如下功能: 从指定网页抓取新闻内容; 使…...
Unity中国战略调整简讯:Unity6下架 团结引擎接棒
Unity中国战略调整简讯:Unity6下架 团结引擎接棒 免费版 2025年4月9日 —— Unity中国宣布自即日起,中国大陆及港澳地区停止提供Unity 6及后续版本下载与服务,相关功能由国产引擎“团结引擎”承接。国际版2022 LTS及更早版本仍由Unity中国维护…...
司美格鲁肽用SNAC市场报告:2024年全球市场销售额达到了0.14亿美元
引言:了解司美格鲁肽与SNAC的重要性 在当前的医药领域,司美格鲁肽(Semaglutide)作为一种创新性的治疗2型糖尿病和肥胖症的药物,受到了广泛关注。而SNAC(N-(8-(2-羟苯基)…...
自动驾驶第一性原理
所谓的第一性原理: 就是指从最基本的物理规律,数据逻辑及工程约束条件出发,剥离所有的非本质的假设,直接推导出自动驾驶最核心的要素。 自动驾驶核心框架分解: 1、根本目标: 安全高效的将人/物从A地运送…...
《UE5_C++多人TPS完整教程》学习笔记36 ——《P37 拾取组件(Pickup Widget)》
本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P37 拾取组件(Pickup Widget)》 的学习笔记,该系列教学视频为计算机工程师、程序员、游戏开发者、作家(Engineer, Programmer, Game Developer, Author) Steph…...
Uniswap V2/V3/V4 流动性与价格计算详解
Uniswap V2/V3/V4 流动性与价格计算详解 一、核心概念对比 Uniswap V2 流动性模型: 恒定乘积公式 (x * y = k)价格决定: 完全由池子中的代币数量决定 (price = y/x)流动性衡量: 总储备量代表流动性,直接通过 getReserves() 获取流动性分布: 均匀分布在所有价格点交易费用: 固…...
yum安装MySQL数据库
yum安装方式 优点:操作简单易用。不用单独下载,服务器可以联网且yum源没有问题即可(可以选择国内的163/阿里源) 安装步骤: 1.关闭防火墙和selinux: systemctl stop firewalld ##关闭防火墙 systemctl disable firewalld …...
大联盟(特别版)双端互动平台完整套件分享:含多模块源码+本地部署环境
这是一套结构清晰、功能完整的互动平台组件,适合有开发经验的技术人员进行模块参考、结构研究或本地部署实验使用。 该平台覆盖前端展示、后端服务、移动端资源以及完整数据库,采用模块化架构,整体部署流程简单清晰,适合自研团队参…...
【Code】《代码整洁之道》笔记-Chapter15-JUnit内幕
第15章 JUnit内幕 JUnit是最有名的Java框架之一。就像别的框架一样,它概念简单,定义精确,实现优雅。但它的代码是怎样的呢?本章将研判来自JUnit框架的一个代码例子。 15.1 JUnit框架 JUnit有很多位作者,但它始于K…...
【Java八股】
JVM JVM中有哪些引用 在Java中,引用(Reference)是指向对象的一个变量。Java中的引用不仅仅有常规的直接引用,还有不同类型的引用,用于控制垃圾回收(GC)的行为和优化性能。JVM中有四种引用类型…...
深入探究AI编程能力:ChatGPT及其大规模模型的实现原理
📢 友情提示: 本文由银河易创AI(https://ai.eaigx.com)平台gpt-4-turbo模型辅助创作完成,旨在提供灵感参考与技术分享,文中关键数据、代码与结论建议通过官方渠道验证。 随着人工智能的快速发展,…...
高德地图 JS-SDK 实现教程
高德地图 JS-SDK 实现教程:定位、地图选点、地址解析等 适用地点选择、地址显示、表单填写等场景,全面支持移动端、手机浏览器和 PC端环境 一、创建应用&Key 前端(JS-SDK、地图组件) 登陆 高德开放平台创建应用,…...
【信息系统项目管理师】高分论文:论信息系统项目的整合管理(银行数据仓库项目)
更多内容请见: 备考信息系统项目管理师-专栏介绍和目录 文章目录 正文一、制定项目章程二、制定项目管理计划三、指导和管理项目的实施四、管理项目知识五、监控项目工作六、实施整体变更控制七、结束项目或阶段正文 2023年6月,我以项目经理的身份,参加了 xx银行xx省分行数…...
dev中使用auto的方法
在dev-c中使用新特性是一样的道理,在他启动编译器来编译代码的时候我们让他加上这个参数就行了,设置方法是:在Tools里面找到Compiler Options打开它,然后把那个Add the following commands when calling compiler:选上勾,在里面加…...
C 语言中经典的数据结构
在 C 语言中,经典的数据结构通常包括以下几种,每种都有其特定的应用场景和实现方式: 1. 数组(Array) 定义:连续内存空间存储相同类型的数据。 特点:随机访问快(O(1))&am…...
小白学习java第12天(下):网络编程
上面我们了解TCP就是三次握手!!! 下面我们就详细介绍一下UDP,就是进行发包(TCP协议类似于就是打电话,你必须进行连接才能进行传输,但是UDP类似于发消息,连不连接我都是可以的&#…...
论文精度:双分支图Transformer网络:视频驱动的3D人体网格重建新突破
论文地址:https://arxiv.org/pdf/2412.01179 目录 一、背景与问题定义 1.1 3D人体网格重建的意义 1.2 现有方法的困境 二、核心创新:DGTR网络架构 2.1 整体框架设计 2.2 全局运动感知分支(GMA) 2.3 局部细节优化分支(LDR) 2.3.1 局部信息聚合 2.3.2 调制图卷积…...
华三IRF堆叠技术
IRF(Intelligent Resilient Framework,智能弹性架构)是华三通信(H3C)自主研发的网络设备虚拟化技术,通过将多台物理设备整合为单一逻辑设备,实现统一管理、高可靠性和灵活扩展。以下是其核心要点…...
第一阶段补充知识
目录 书写脚本使用的相关知识? 备份和冗灾的区别?什么叫DD备份,什么叫DD冗灾? 关于Linux系统优化以及Linux的安全加固? 系统优化 硬件系统优化: 内核参数优化: 网络性能优化: 进程管…...
STM32 HAL库 L298N电机驱动模块实现
一、引言 在机器人、自动化设备等众多应用场景中,电机驱动是一个关键的部分。L298N 是一款常用的电机驱动模块,它可以驱动两个直流电机或一个步进电机。STM32F407 是一款高性能的 ARM Cortex-M4 内核微控制器,结合 HAL 库可以方便地实现对 L…...
Redis的Key的过期策略
我们都知道Redis的键值对是可以设置过期时间的,那么就会涉及到一个问题,Redis到底是如何做到响应快的同时有能快速地释放掉过期的键值对的呢?不卖关子了,直接说答案,那就是Redis两个策略:定期删除和惰性删除…...
ubuntu桌面版使用root账号进行登录
这里写自定义目录标题 第一步:给root账户设置密码,并切换至root账户第二步:注释gdm-autologin文件内的相关内容第三步:注释gdm-password文件内的相关内容第四步:重启系统即可使用root账户登录 第一步:给roo…...
贪心算法(18)(java)距离相等的条形码
在一个仓库里,有一排条形码,其中第 i 个条形码为 barcodes[i]。 请你重新排列这些条形码,使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案,此题保证存在答案。 示例 1: 输入:barco…...
CentOS服务器能ping通却无法yum install:指定镜像源解决
文章目录 前言一、问题记录二、解决过程1.修改DNS无效2.指定镜像源 总结 前言 今天有一个项目现场要在一个远程centos服务器上部署产品服务,发现能ping通百度,但是无法yum install 安装基础软件包,开始以为DNS服务器的问题,结果配…...
WebSocket与MQTT
在物联网(IoT)领域,WebSocket和MQTT确实都可以实现实时通信,但它们的核心设计目标、适用场景和角色存在显著差异。以下是两者的对比分析: 1. 协议设计初衷 WebSocket 目标:提供浏览器与服务器…...
【论文解读】MSVM-UNet: Multi-Scale Vision Mamba UNet for Medical Image Segmentation
MSVM-UNet: Multi-Scale Vision Mamba UNet for Medical Image Segmentation 论文链接: https://arxiv.org/abs/2408.13735 Code: https://github.com/gndlwch2w/msvm-unet 来源: 2024 IEEE International Conference on Bioinformatics an…...
Vue表单组件el-form校验规则rules,条件判断rules表单验证显示必填或非必填
在使用 Element UI(一个基于 Vue 的前端框架)的表单验证功能时,你可能想要实现一个规则,使得某些字段在特定条件下成为必填项,或者在满足某些条件时不允许为空。这通常通过自定义校验规则来实现。 <template>&l…...
手动关闭ArcGIS与ArcGIS Online连接的方法
【关闭软件启动时ArcGIS与ArcGIS Online连接方法】 打开C盘找到文件夹“C:\Program Files (x86)\Common Files\ArcGIS\bin”,如下图,删除“ArcGISConnection.exe”与“ArcGISConnectionTest.exe”文件,软件下次启动的时候就不会建立与ArcGIS …...
(二十五)安卓开发一个完整的登录页面-支持密码登录和手机验证码登录
下面将详细讲解如何在 Android 中开发一个完整的登录页面,支持密码登录和手机验证码登录。以下是实现过程的详细步骤,从布局设计到逻辑实现,再到用户体验优化,逐步展开。 1. 设计登录页面布局 首先,我们需要设计一个用…...
【过程控制系统】PID算式实现,控制系统分类,工程应用中控制系统应该注意的问题
目录 1-1 试简述过程控制的发展概况及各个阶段的主要特点。 1-2 与其它自动控制相比,过程控制有哪些优点?为什么说过程控制的控制过程多属慢过程? 1-3 什么是过程控制系统,其基本分类是什么? 1-4 何为集散控制系统…...
测试第三课-------自动化测试相关
作者前言 🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂 🎂 作者介绍: 🎂🎂 🎂 🎉🎉🎉…...
关于数据清洗和数据处理实践学习笔记
一些可能想要知道的: pandas是一个模板,它读取的数据都是dataframe的格式,即df Matplotlib是一个用于数据可视化的Python库,能够生成各种静态、动态和交互式图表 pyplot:Matplotlib 的核心接口模块,提供类…...
ubuntu学习day2
linux常用命令 3.文件查看及处理命令 3.1查看文件内容 cat[选项][文件] -b 对非空输出行编号 -E 在每行结束处显示$ -n 对输出的所有行编号 -s 不输出多行空行 标准输入、标准输出和标准错误 在 Linux 中,每个进程默认有三个文件描述符: 标准输入&…...
JavaScript `new Date()` 方法移动端 `兼容 ios`,ios环境new Date()返回NaN
在 iOS 环境下,new Date() 方法会返回 NaN,这通常是由于时间字符串的格式问题。iOS 的 Date 构造函数对时间字符串的格式要求比其他平台更严格。 原因:ios端不兼容“-”为连接符的时间。 解决办法: 替换时间格式 IOS 不支持某…...
考研408参考用书:计算机组成原理(唐朔飞)介绍,附pdf
我用夸克网盘分享了「《计算机组成原理》第2,3版 唐朔飞」, 链接:https://pan.quark.cn/s/6a87d10274a3 1. 书籍定位与适用对象 定位:计算机组成原理是计算机科学与技术、软件工程等专业的核心基础课程,涉及计算机硬件的底层工作原…...
案例-索引对于并发Insert性能优化测试
前言 最近因业务并发量上升,开发反馈对订单表Insert性能降低。应开发要求对涉及Insert的表进行分析并提供优化方案。 一般对Insert 影响基本都在索引,涉及表已按创建日期做了分区表,索引全部为普通索引未做分区索引。 优化建议ÿ…...
@Async 为什么要自定义线程池,使用默认线程池风险
为什么要自定义线程池而非使用默认线程池 使用Spring的Async注解时,如果不自定义线程池而使用默认线程池,可能会带来一些风险和问题。以下是主要原因: 默认线程池的风险 无限制的资源消耗 默认线程池使用SimpleAsyncTaskExecutor࿰…...
Spark-SQL简介与编程
1. Spark-SQL是什么 Spark SQL 是 Spark 用于结构化数据(structured data)处理的 Spark 模块。 Hadoop与Spark的对比 Hadoop的局限性 Hadoop无法处理结构化数据,导致一些项目无法推进。 例如,MySQL中的数据是结构化的,Hadoop无法直接处理。…...
如何分析 JVM OOM 内存溢出 Dump 快照日志
文章目录 1、需求背景2、OOM 触发3、Dump 日志分析 1、需求背景 企业开发过程中,如果系统服务客户量比较大,偶尔会出现OOM内存溢出问题,导致服务发生宕机,停止对外提供访问。 这种情况就需要排查定位内存溢出的原因(…...
系统监控 | 简易多个内网服务器的CPU和内存使用率监控 system_moniter
效果图 原理 一台主机A上运行mysql数据库,接收数据。 其他主机设置定时任务,每6分钟发送一次自己的CPU和内存使用百分数到主机A。 主机A上提供flask为后台的可视化网页,见上图。 源码库 https://github.com/BioMooc/system_moniterhttps:/…...
【神经网络】python实现神经网络(四)——误差反向传播的基础理论
一.反向传播 本章将介绍能够高效计算权重参数的梯度的方法——误差反向传播法,这里简单介绍一下什么是反向传播,加入有个函数y = f(x),那么它的反向传播为图下这个样子: 反向传播的计算顺序是,将输入信号E乘以节点的局部导数,然后将结果传递给下一个节点。这里所…...
Django 开发服务器
$ python manage.py runserver $ python manage.py runserver 666 # 用 666 端口 $ python manage.py runserver 0.0.0.0:8000 # 让局域网内其他客户端也可访问 $ python manage.py runserver --skip-checks # 跳过检查自动检查 $ python manage.py runserver --…...
嵌入式基础(二)ARM基础
嵌入式基础(二)ARM基础 1.精简指令集和复杂指令集的区别⭐⭐⭐ 精简指令集 (RISC) 精简指令集 (Reduced Instruction Set Computing) 具有简洁、精简的指令集,每条指令执行的操作都很基础,使得处理器设计更简单。RISC 处理器通…...
RNA免疫共沉淀测序(RIP-seq)
技术简介 RNA免疫共沉淀测序(RNA Immunoprecipitation Sequencing, RIP-seq)是一种将RNA免疫共沉淀(RIP)与二代测序技术(NGS)相结合,用于研究细胞内RNA与蛋白相互作用的技术。 技术原理 利用目…...