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

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&#xff1a; 一本通&#xff1a;http://ybt.ssoier.cn:8088/problem_show.php?pid1950 解法一、朴素模拟 核心思想&#xff1a; 朴素模拟&#xff1a; 1、先给每个b[i]水龙头分配一个人a[i]&#xff0c;b[i] 表示水龙头的剩余时间。同时标记该水龙头为 used 使用中 2…...

ElementUI从unpkg.com完整下载到本地的方法 - 解决unpkg.com不稳定的问题 - 自建镜像站 - 不想打包只想cdn一下

方法 方法1&#xff09;随便弄个文件夹&#xff0c;根据官网npm方法下载包&#xff0c;提取即可 npm i element-ui -S cd /node_modules/element-ui/ ls src 安装npm方法&#xff1a;https://nodejs.org/en 方法2&#xff09;不推荐 - 在github中搜索对应的库zip包&#xff0…...

什么是BFF API

BFF&#xff08;Backend For Frontend&#xff09;API 是一种架构模式&#xff0c;旨在为特定的前端应用&#xff08;如移动应用、桌面应用或网页应用&#xff09;提供定制化的后端服务。通过这种方式&#xff0c;后端可以根据前端的具体需求和特性&#xff0c;提供最优化的数据…...

分享自己一篇在亚马逊云科技AWS官网发的Blog技术文章

小李哥在亚马逊AWS官网&#xff0c;作为第一作者发了自己的第一篇AWS Blog文章&#xff0c;也是自己今年在AWS官网的第11篇文章。文章主要内容是描述为出海的金融企业&#xff0c;搭建满足PCI-DSS合规、FIPS 140-2 Level 3安全标准的传输中数据加密云端方案&#xff0c;主要用于…...

封装长按触发事件的uniapp组件

简单说一下原理 首先介绍三个针对触摸屏设备的事件&#xff0c;分别是&#xff1a; touchstart&#xff1a;当手指触摸屏幕时触发&#xff0c;即触摸开始的时候&#xff1b;touchend&#xff1a;当手指离开屏幕时触发&#xff0c;即触摸结束的时候&#xff1b;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备份库&#xff0c;注意密码与-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 端口与时间服务器定时同步时间&#xff0c;默认的配置文件是 /etc/chrony.conf chronyc 通过 323 端口与 chronyd 交互&#xff0c;可监控 chronyd 的性能并在运…...

前端开发框架Vue

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl Vue概述 Vue.js&#xff08;简称Vue&#xff09;是由尤雨溪&#xff08;Evan You&#xff09;创建并维护的一款开源前端开发框架。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…...

华中科技大学雷达站部署

一&#xff1a;项目地址 GitHub - HUSTLYRM/HUST_Radar_2023: 华中科技大学狼牙战队 RoboMaster 2023赛季 雷达站 二&#xff1a;安装依赖 2.1创建虚拟环境 首先是程序是基于python3.8完成&#xff0c;所以创建虚拟环境的时候&#xff0c;选择3.8的虚拟环境 conda create -…...

小程序引入 Vant Weapp 极简教程

一切以 Vant Weapp 官方文档 为准 Vant Weapp 官方文档 - 快速入手 1. 安装nodejs 前往官网下载安装即可 nodejs官网 安装好后 在命令行&#xff08;winr&#xff0c;输入cmd&#xff09;输入 node -v若显示版本信息&#xff0c;即为安装成功 2. 在 小程序根目录 命令行/终端…...

labview技术交流-将时间字符串转换成时间格式

应用场景 我们在数据库中设计了datetime类型的字段&#xff0c;比如字段名就叫“保存时间”&#xff0c;当我们使用labview将表中数据读取出来后datetime类型的数据是以字符串的格式显示的。而我们想计算两条数据“保存时间”的间隔时间时&#xff0c;用字符串类型自然是没法计…...

算法提高之迷宫问题

算法提高之迷宫问题 核心思想&#xff1a;最短路问题 从(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开发 通过点击按钮来复制选择的明细行 复制明细行功能背景展示效果实现方法 复制明细行 功能背景 用户可以通过“复制明细”按钮来实现新增选择的明细行&#xff0c;并且新增明细行的数据跟选择的数据完全一样&#xff0c;具体操作如下图所示&#xff1a; 手动新增明细…...

sqlalchemy 分表实现方案

1.需求及场景概述 现有系统中因历史数据量过大&#xff0c;产生了将历史数据进行按月存储的要求&#xff0c;系统和数据库交互使用的是sqlalchemy&#xff0c;假设系统的原来的历史记录表&#xff08;record&#xff09;如下&#xff1a; 为了将历史数据按月分表存储&#xff0…...

QML进阶(十五) QML各种标准元素的用法

文章目录 文本图像控件TextTextInputTextFieldTextEditTextAreaImage按钮控件ButtonRadioButtonCheckBoxComboBox进度控制控件ProgressBarSlider...

【工具使用】快速实现Makefile模板的方法

一&#xff0c;简介 我们在使用gcc编译程序时&#xff0c;常常需要自己实现Makefile&#xff0c;那么如何快速的实现Makefile呢&#xff1f;这里把一些基本的操作整理成模板&#xff0c;供参考。 二&#xff0c;模板介绍 功能包含基本功能编译exe&#xff08;包括调用其他算…...

Linux-信号执行

1. 信号什么时候被处理 当进程从内核态返回到用户态的时候&#xff0c;进行信号的检测和处理 什么内核态&#xff0c;什么又是用户态呢&#xff1f; 当进程在CPU上运行时&#xff0c;内核态&#xff1a;允许进程访问操作系统的代码和数据&#xff0c;用户态&#xff1a;进程只…...

在线听歌播放器 梨花带雨网页音乐播放器 网页音乐在线听 源码

最新梨花带雨网页音乐播放器二开优化修复美化版全开源版本源码下载 下 载 地 址 &#xff1a; runruncode.com/php/19749.html 梨花带雨播放器基于thinkphp6开发的XPlayerHTML5网页播放器前台控制面板,支持多音乐平台音乐解析。二开内容&#xff1a;修复播放器接口问题&am…...

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

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

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

ArcPy扩展模块的使用(3)

管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如&#xff0c;可以更新、修复或替换图层数据源&#xff0c;修改图层的符号系统&#xff0c;甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...

路由基础-路由表

本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中&#xff0c;往往存在多个不同的IP网段&#xff0c;数据在不同的IP网段之间交互是需要借助三层设备的&#xff0c;这些设备具备路由能力&#xff0c;能够实现数据的跨网段转发。 路由是数据通信网络中最基…...

联邦学习带宽资源分配

带宽资源分配是指在网络中如何合理分配有限的带宽资源&#xff0c;以满足各个通信任务和用户的需求&#xff0c;尤其是在多用户共享带宽的情况下&#xff0c;如何确保各个设备或用户的通信需求得到高效且公平的满足。带宽是网络中的一个重要资源&#xff0c;通常指的是单位时间…...

uni-app学习笔记二十三--交互反馈showToast用法

showToast部分文档位于uniapp官网-->API-->界面&#xff1a;uni.showToast(OBJECT) | uni-app官网 uni.showToast(OBJECT) 用于显示消息提示框 OBJECT参数说明 参数类型必填说明平台差异说明titleString是提示的内容&#xff0c;长度与 icon 取值有关。iconString否图…...