接水问题-题解_#482. 【基础】接水问题题解-程序员宅基地

接水问题

(2010普及) 题解 2020.04.19

读题:

学校里有一个水房,水房里一共装有m个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为 1。
现在有n名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号, i号同学的接水量为 w[i]。
接水开始时,1到 m 号同学各占一个水龙头,并同时打开水龙头接水。
当其中某名同学j完成其接水量要求 w[j] 后,下一名排队等候接水的同学k马上接替 j同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即j同学第 x秒结束时完成接水,则 k同学第x+1 秒立刻开始接水。
若当前接水人数n’不足m,则只有n’个龙头供水,其它m−n’个龙头关闭。
现在给出 n名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。

输入格式:
第 1 行 2 个整数 n 和 m,用一个空格隔开,分别表示接水人数和龙头个数。
第 2 行 n 个整数:w[1],w[2],……,w[n] ,每两个整数之间用一个空格隔开,w[i] 表示i号同学的接水量。
输出格式:
1 个整数,表示接水所需的总时间。

样例1:
输入:5 3 4 4 1 2 1
输出:4
样例2:
8 4 23 71 87 32 70 93 80 76
输出:163

原题链接(洛谷)

分析:

这是一道模拟+贪心题。

我们来分析一下样例1的说明:

秒数 同学1 同学2 同学3 同学4 同学5
1 3 3 0 2 1
2 2 2 - 1 1
3 1 1 - 0 1
4 0 0 - - 0
答案:4 - - - - -

我们可以看到:
当水龙头都被占满的时候,要等到一个人接满(还需接的水量为0)之后,才会产生新的变化。
而这个人是谁呢?
就是值最小的人
新的变化是什么?
下一(或多)个人补上值最小的一(或多)个人的空缺

当然,水龙头一开始没有人,所以我们要先使m个人占在水龙头上:

	int slt[105]={
   
    0},k=1;//用slt表示m(≤100)个水龙头,k表示即将接水的人的下标
	for(int i=1;i<=m;i++)	slt[i]=w[k++];//将w[1-m]放进stl[1-m]中,此时k=m+1(注意要写成k++,而不是++k,即先slt[i]=w[k]再+
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ZouTYqd/article/details/105612884

智能推荐

css 涟漪,CSS3 涟漪形图案动效-程序员宅基地

文章浏览阅读331次。CSS语言:CSSSCSS确定@-webkit-keyframes pulse {0% {box-shadow: 0 0 0 0;color: #fff;background: #fff;}}@keyframes pulse {0% {box-shadow: 0 0 0 0;color: #fff;background: #fff;}}@-webkit-keyframes pulse-invert..._.body_three::after

linux下,redis 3.2.1双节点集群安装部署-程序员宅基地

文章浏览阅读468次。为什么80%的码农都做不了架构师?>>> ..._linux redis双节点安装部署

最全面的AI学习路线和资源整理-程序员宅基地

文章浏览阅读1.2k次,点赞2次,收藏18次。目录大纲基础知识1.数学2 统计学3 编程数据分析/挖掘1数据分析的基础书籍2特征工程3 数据挖掘项目机器学习公开课 吴恩达《Machine Learning》公开课 吴恩达 CS229公开课 林轩田《机器学习基石》公开课 林轩田《机器学习技法》书籍《机器学习》书籍《统计学习方法》书籍《Scikit-Learn 与 TensorFlow 机器学习实用指南》实战 Kaggle 比赛工具 Sciki...

SpringBoot-2.3.4集成MybatisPlus-3.4.0(gradle)_spring 2.3.4.release用哪个版本的mybatis-程序员宅基地

文章浏览阅读446次。SpringBoot-2.3.4集成MybatisPlus-3.4.0MybatisPlus官方文档版本环境IntelliJ IDEA:2020.1.2java:jdk-14.0.1springboot:v2.3.4.RELEASEgradle:gradle-6.7-rc-4springfox(swagger):version: '3.0.0'swagger-bootstrap-ui:version: '1.9.6'mysql-connector-java:version: '8.0.16_spring 2.3.4.release用哪个版本的mybatis

人工机器:基于视觉的机械手控制_机器视觉控制机械手的具体过程-程序员宅基地

文章浏览阅读5k次。 《机器人学、机器视觉与控制》一书中,第五部分开始,第15章之前——基于视觉的控制,第442页这样写到。 第二个问题:确保机器人能达到一个期望的位姿,也不是一个简单的事情。正如我们在第七章讨论的那样,机器人末端执行器要通过计算要求的关节角度才能向一个位姿运动。这就要求机器人的运动模型是准确的,它反过来就要要求机器人的加工精度必须非常高:连杆长度必须准确,关节轴之间..._机器视觉控制机械手的具体过程

Android 上自定义的复式折线图(一)_andriod 自定义折线图多条-程序员宅基地

文章浏览阅读1.6k次,点赞3次,收藏5次。最近公司想做一个表格统计图,而且要符合可以多条折线的那种,自己也是翻阅了好多资料也没有找到很合适的一种,后来果断决定还是自己定义一个咯,下面先附上效果图.这里有三条折线,其实里面是有两个列表:一个是管颜色的,另一个是管折线上的数据.同时这里的控件外面也包了一个HorizontalScrollView,当超过屏幕时就可以进行水平滚动.而且这里的控件LineView也提供了很过设置属性的方法._andriod 自定义折线图多条

随便推点

约瑟夫环——POJ3379-程序员宅基地

文章浏览阅读1.4k次。题目描述:给出一个长度是n的字符串环,每次搁k个加入字符串中对应位置的字母序的下一个字母,执行m次,问最后一次插入的是什么字母。大致思路:正着想的话只能用模拟的方法解决,但是m有10^9这么大,而把问题倒过来想一下的话,那就变成了给出一个n+m的字符串每次搁k个字符删掉一个,最后剩下一个长度为n的字符串,问起始位置是什么字母。这样的话就变成了约瑟夫问题,约瑟夫环问题可以在不用考虑内容的_poj3379

Gym - 101652P Fear Factoring-程序员宅基地

文章浏览阅读220次。Fear Factoring 题 意:输入a,b让你求[a,b]所有的数的因数和。 数据范围: 1&amp;lt;=a&amp;lt;=b&amp;lt;=1e12 0&amp;lt;=b-a&amp;lt;=1e6输入样例:101 101输出样例:102思 路:我们先求这个[1,n]所有的数因数和,然后用cal(b)-cal(a-1)就是[a,b]内的所有因数和了。问题是怎么求这个cal(b)呢?用的是除法..._gym - 101652p

jQuery中的closest()和parents()的区别_jquery closest 和parents 区别-程序员宅基地

文章浏览阅读1.9k次。jQuery中的closest()和parents()的区别jQuery中closest()和parents()的作用非常相似,都是向上寻找符合选择器条件的元素,但是他们之间有一些细微的差别,官网也给出了说明: .closest() .parents() Begins with the current element Begins with the parent element T_jquery closest 和parents 区别

踩坑记 | Flink 天级别窗口中存在的时区问题-程序员宅基地

文章浏览阅读1.7k次。本系列每篇文章都是从一些实际的 case 出发,分析一些生产环境中经常会遇到的问题,抛砖引玉,以帮助小伙伴们解决一些实际问题。本文介绍 Flink 时间以及时区问题,分析了在天级别的窗口..._flink时区报错

安装yii2.0 advanced_yii advance 汉化版-程序员宅基地

文章浏览阅读295次。1.在官网上下载(http://www.yiiframework.com/download/)选择 advanced 版2.解压到D:\phpStudy\WWW\ 并且改名为blogdemo2 phpstudy配置好hosts和站点域名3.初始化模板 打开cmd切换到 项目所在路径,运行php init ,选择开发模式 0 ,然后yes 4.打开_yii advance 汉化版

小程序 ----踩坑 ---安卓iOS兼容等-程序员宅基地

文章浏览阅读567次。关于小程序一些小功能的代码都在这个GitHub上,感兴趣的可以去看看,https://github.com/huihuijiang/miniProgram目前有:列表左滑删除,拖拽浮标一、小程序坑1.scroll-view横向滚动的时候,包含文字图片等,元素错位,第二个元素掉下去;hack:给子元素添加vertical-align:top;当使用scroll-view横..._小程序 ios parsefloat