2010NOIP普及组真题 2. 接水问题
线上OJ:
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1950
解法一、朴素模拟
核心思想:
朴素模拟:
1、先给每个b[i]水龙头分配一个人a[i],b[i] 表示水龙头的剩余时间。同时标记该水龙头为 used 使用中
2、每一次 while 循环表示1秒,即接水时间+1。同时每个水龙头的剩余时间 b[i]–。
3、如果某个水龙头的剩余时间 b[i] 减到了0,则把队列中的 a[j] 分配给b[i]。同时 j++ 指向下一个人
4、如果某个水龙头的剩余时间 b[i] 减到了0,但是队伍中已经没有排队等待接水的人了(j>n),则设置used[i] = 0 表示关闭 b[i] 水龙头,同时关闭的数量 cnt++
5、当关闭水龙头的数量 cnt==n 时,说明所有水龙头都已经关闭,此时的接水时间 t 就是最终结果
题解代码:
#include <bits/stdc++.h>
using namespace std;const int M = 105, N = 10005;
int a[N], b[M], used[M]={0};
int n, m;int main()
{scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= m; i++){b[i] = a[i]; // 初始分配水龙头used[i] = 1; // 该水龙头标记为使用中}int t = 0, cnt = 0; // t表示总接水时间,cnt表示关闭的水龙头数量int j = m + 1; // 由于前m个水龙头都已经初始分配了,故第一个等待排队的是 m+1while(cnt < m) // 跳出条件:水龙头全部关闭{t++; // 总接水时间++for(int i = 1; i <= m; i++) // 循环m个水龙头{if(used[i]) // 如果当前水龙头在使用中{b[i]--; // 则b[i]--if(b[i] == 0) // 如果 b[i] 减到0{if(j<= n) b[i] = a[j++]; // 如果还有人在排队,则第一个排队的人接到b[i]else // 如果没人在排队{used[i] = 0; // 则关闭该水龙头cnt++; // 关闭数量++}}}}}printf("%d\n", t);return 0;
}
解法二、模拟排队
思考:
现实生活中如果我们去打水,肯定看哪个队伍短就排在哪个队伍后面。
本题也是一样,
1、看哪个队伍的打水时间最短,就排在哪个队伍后面,同时 更新该队伍的打水时间。
2、n个人就处理n次
3、n次以后,打水时间最长的队伍就是题解

题解代码:
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;const int M = 105;
int b[M]; // b[i]表示每个水龙头的打水时间
int n, m, a;
int minn, ans; // ans记录最终结果/*
思考:现实生活中如果我们去打水,肯定看哪个队伍短就排在哪个队伍后面。
本题也是一样,看哪个队伍的打水时间最短,就把当前排队的人接在哪个队伍后面,同时更新该队伍的打水时间。
*/
int main()
{scanf("%d %d", &n, &m);// 读入每个人的打水时间,并将其接在当前打水时间最短的队伍后面for(int i = 1;i <= n; i++) // n个人,分配 n 次队伍,故循环 n 次{scanf("%d", &a);minn = INF;int k = 0;for(int j = 1;j <= m;j++) // 循环m次,找出哪个队伍的打水时间最短if(b[j] < minn){k = j;minn = b[j];}b[k] = b[k] + a; // 将当前的人接在最短的队伍后面,更新打水时间}ans = -INF; // 在最后的队伍中找最长的队伍,这个时间就是最长打水时间for(int i = 1; i <= m; i++) ans = max(ans, b[i]);printf("%d", ans);return 0;
}
相关文章:
2010NOIP普及组真题 2. 接水问题
线上OJ: 一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid1950 解法一、朴素模拟 核心思想: 朴素模拟: 1、先给每个b[i]水龙头分配一个人a[i],b[i] 表示水龙头的剩余时间。同时标记该水龙头为 used 使用中 2…...
ElementUI从unpkg.com完整下载到本地的方法 - 解决unpkg.com不稳定的问题 - 自建镜像站 - 不想打包只想cdn一下
方法 方法1)随便弄个文件夹,根据官网npm方法下载包,提取即可 npm i element-ui -S cd /node_modules/element-ui/ ls src 安装npm方法:https://nodejs.org/en 方法2)不推荐 - 在github中搜索对应的库zip包࿰…...
什么是BFF API
BFF(Backend For Frontend)API 是一种架构模式,旨在为特定的前端应用(如移动应用、桌面应用或网页应用)提供定制化的后端服务。通过这种方式,后端可以根据前端的具体需求和特性,提供最优化的数据…...
分享自己一篇在亚马逊云科技AWS官网发的Blog技术文章
小李哥在亚马逊AWS官网,作为第一作者发了自己的第一篇AWS Blog文章,也是自己今年在AWS官网的第11篇文章。文章主要内容是描述为出海的金融企业,搭建满足PCI-DSS合规、FIPS 140-2 Level 3安全标准的传输中数据加密云端方案,主要用于…...
封装长按触发事件的uniapp组件
简单说一下原理 首先介绍三个针对触摸屏设备的事件,分别是: touchstart:当手指触摸屏幕时触发,即触摸开始的时候;touchend:当手指离开屏幕时触发,即触摸结束的时候;touchcancel&am…...
Docker 安装的MySQL迁移数据库
1. 导出数据库 docker ps :查看数据库对应的 CONTAINER ID docker exec -it id /bin/bash : 进入到mysql的docker实例中 cd /usr/bin : 进入到bin目录 mysqldump -u root -p123456 study > /root/study_backup0509.sql :使用mysqldump备份库,注意密码与-p之间…...
算法训练Day28 | ● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II
122.买卖股票的最佳时机II class Solution { public:int maxProfit(vector<int>& prices) {vector<int> dp(2,0);dp[0] -prices[0];for(int i1; i<prices.size(); i){dp[0] max(dp[0], dp[1]-prices[i]);dp[1] max(dp[1], prices[i]dp[0]);}return dp[1]…...
Linux(openEuler、CentOS8)基于chrony企业内网NTP服务器搭建实验
一、知识点 chrony 是由 守护进程 chronyd 以及 命令行工具 chronyc 组成的 chronyd 在后台静默运行并通过 123 端口与时间服务器定时同步时间,默认的配置文件是 /etc/chrony.conf chronyc 通过 323 端口与 chronyd 交互,可监控 chronyd 的性能并在运…...
前端开发框架Vue
版权声明 本文原创作者:谷哥的小弟作者博客地址:http://blog.csdn.net/lfdfhl Vue概述 Vue.js(简称Vue)是由尤雨溪(Evan You)创建并维护的一款开源前端开发框架。Vue以其轻量级、易上手和高度灵活的特点&…...
Vue2中引入ElementUI
Vue中引入ElementUI 目录 Vue中引入ElementUI安装 全库导入main.py使用 仅引入样式文件main.py使用 安装 官方文档 npm i element-ui -S全库导入 main.py import ElementUI from element-ui;Vue.use(ElementUI)使用 <template> <div class"main">&l…...
华中科技大学雷达站部署
一:项目地址 GitHub - HUSTLYRM/HUST_Radar_2023: 华中科技大学狼牙战队 RoboMaster 2023赛季 雷达站 二:安装依赖 2.1创建虚拟环境 首先是程序是基于python3.8完成,所以创建虚拟环境的时候,选择3.8的虚拟环境 conda create -…...
小程序引入 Vant Weapp 极简教程
一切以 Vant Weapp 官方文档 为准 Vant Weapp 官方文档 - 快速入手 1. 安装nodejs 前往官网下载安装即可 nodejs官网 安装好后 在命令行(winr,输入cmd)输入 node -v若显示版本信息,即为安装成功 2. 在 小程序根目录 命令行/终端…...
labview技术交流-将时间字符串转换成时间格式
应用场景 我们在数据库中设计了datetime类型的字段,比如字段名就叫“保存时间”,当我们使用labview将表中数据读取出来后datetime类型的数据是以字符串的格式显示的。而我们想计算两条数据“保存时间”的间隔时间时,用字符串类型自然是没法计…...
算法提高之迷宫问题
算法提高之迷宫问题 核心思想:最短路问题 从(n-1,n-1)开始bfs 往前走一个就存入pre数组 之后再遍历pre数组输出 #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N 1010,M N*N;#define x first#def…...
泛微E9开发 通过点击按钮来复制选择的明细行
泛微E9开发 通过点击按钮来复制选择的明细行 复制明细行功能背景展示效果实现方法 复制明细行 功能背景 用户可以通过“复制明细”按钮来实现新增选择的明细行,并且新增明细行的数据跟选择的数据完全一样,具体操作如下图所示: 手动新增明细…...
sqlalchemy 分表实现方案
1.需求及场景概述 现有系统中因历史数据量过大,产生了将历史数据进行按月存储的要求,系统和数据库交互使用的是sqlalchemy,假设系统的原来的历史记录表(record)如下: 为了将历史数据按月分表存储࿰…...
QML进阶(十五) QML各种标准元素的用法
文章目录 文本图像控件TextTextInputTextFieldTextEditTextAreaImage按钮控件ButtonRadioButtonCheckBoxComboBox进度控制控件ProgressBarSlider...
【工具使用】快速实现Makefile模板的方法
一,简介 我们在使用gcc编译程序时,常常需要自己实现Makefile,那么如何快速的实现Makefile呢?这里把一些基本的操作整理成模板,供参考。 二,模板介绍 功能包含基本功能编译exe(包括调用其他算…...
Linux-信号执行
1. 信号什么时候被处理 当进程从内核态返回到用户态的时候,进行信号的检测和处理 什么内核态,什么又是用户态呢? 当进程在CPU上运行时,内核态:允许进程访问操作系统的代码和数据,用户态:进程只…...
在线听歌播放器 梨花带雨网页音乐播放器 网页音乐在线听 源码
最新梨花带雨网页音乐播放器二开优化修复美化版全开源版本源码下载 下 载 地 址 : runruncode.com/php/19749.html 梨花带雨播放器基于thinkphp6开发的XPlayerHTML5网页播放器前台控制面板,支持多音乐平台音乐解析。二开内容:修复播放器接口问题&am…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
高分辨率图像合成归一化流扩展
大家读完觉得有帮助记得关注和点赞!!! 1 摘要 我们提出了STARFlow,一种基于归一化流的可扩展生成模型,它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流(TARFlow&am…...
2025.6.9总结(利与弊)
凡事都有两面性。在大厂上班也不例外。今天找开发定位问题,从一个接口人不断溯源到另一个 接口人。有时候,不知道是谁的责任填。将工作内容分的很细,每个人负责其中的一小块。我清楚的意识到,自己就是个可以随时替换的螺丝钉&…...
嵌入式面试常问问题
以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...
