首页 > [NOIP2010]接水问题
开通博客写题解
头像 savage
发表于 2019-08-26 14:59:44
题目描述 学校里有一个水房，水房里一共装有m个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。 现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号，i号同学的接水量为wi。接水开始时，1到m号同学各占一个水龙头，并同时打开水龙头接 展开全文
去ta的博客 赞 (5) 回复(2) 收起
头像 lkjhxx
发表于 2022-08-05 16:49:12
我一开始写得贼复杂，但我觉得我的想法是对的，只要时间不限就能全 ac 具体思想是： i 记录秒数，j 记录下标，k 记录占用水龙头数 内层 while 循环寻找在接水的同学中接水量最小的。在列表内若 0 跳过，若非 0 则加入排序列表寻找最小值 外层 while 循环记录总时长并在接水同学接水量上减 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 青笙
发表于 2022-01-17 21:32:58
解决此题的关键在于如何算出接水的总时间。我们先用一个数组接收每个人需要打水的量，接下来用for语句控制一次所承载同时接水的人数m，通过遍历得出数组中前m个元素中最小的那个，并用x记录其索引。接下来再用一个for循环来进行同时减最小值，此最小值就代表时间的流逝，也代表此时需要换人接水，也就是p[x]= 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 savage
发表于 2019-09-07 12:28:06
算法：模拟 复杂度： 解题思路： 从前往后依次考虑队列中的每个同学，每个同学会去当前结束时间最早的水龙头处接水。 由于本题数据范围较小，因此可以直接循环一遍所有水龙头，求出当前结束时间最早的水龙头编号。那么我们就将当前同学安排在这个水龙头的位置上，然后将该水龙头的结束时间加 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 左右左
发表于 2021-05-11 15:30:03
include using namespace std;int n,m,ans=0,k=1,res=0;const int p=10010;int q[p];int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”