当前位置:首页 > 复赛 > 正文内容

NOIP2010年普及组T2 接水问题

亿万年的星光4年前 (2021-01-28)复赛23503

【题目描述】

学校里有一个水房,水房里一共装有m 个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为1。

现在有n 名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n 编号,i号同学的接水量为wi。接水开始时,1到m 号同学各占一个水龙头,并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj后,下一名排队等候接水的同学k马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即j 同学第x 秒结束时完成接水,则k同学第x+1 秒立刻开始接水。若当前接水人数n′不足m,则只有n′个龙头供水,其它m−n′个龙头关闭。

现在给出n名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。

【输入描述】

第1 行2 个整数n 和m,用一个空格隔开,分别表示接水人数和龙头个数。

第2 行n 个整数w1、w2、……、wn,每两个整数之间用一个空格隔开,wi 表示i 号同学的接水量。

【输出描述】

只有一行,1 个整数,表示接水所需的总时间。

【输入样例1】

5 3
4 4 1 2 1

【输出样例1】

4

【输入样例1说明】

第1 秒,3 人接水。第1 秒结束时,1、2、3 号同学每人的已接水量为1,3 号同学接完水,4 号同学接替3 号同学开始接水。

第2 秒,3 人接水。第2 秒结束时,1、2 号同学每人的已接水量为2,4 号同学的已接水量为1。

第3 秒,3 人接水。第3 秒结束时,1、2 号同学每人的已接水量为3,4 号同学的已接水量为2。4 号同学接完水,5 号同学接替4 号同学开始接水。

第4 秒,3 人接水。第4 秒结束时,1、2 号同学每人的已接水量为4,5 号同学的已接水量为1。1、2、5 号同学接完水,即所有人完成接水。

总接水时间为4 秒

【样例输入2】

8 4
23 71 87 32 70 93 80 76

【样例输出2】

163

【数据规模】

1≤n≤10000,1≤m≤100且 m<=n;

1≤wi≤100

【分析】

1.不要想的太复杂,不是排队接水(贪心)那种题。

2.开始的队伍已经排好(顺序已经固定),我们只要确定下个人去替代接完水的人的位置。

3.当队伍中有的人接完水后,下一个来接替的人的位置一定是当前队伍中接水最快的那个

4.noip t2 的难度,没有必要用数据结构

5. 第m位同学接水,下一名同学是m+1

【思路1】

纯暴力模拟,按照时间和总接水量模拟

#include<bits/stdc++.h>
using namespace std;
int n,m,t; //定义n个人,m个水龙头,时间
int w[10005]; //存储每个人的接水量
int nextt,sum; //下一个接水的人的编号,总接水量
int main()
{
   cin>>n>>m;
   next=m+1; //有m个水龙头,就有m个人接水,下一个一定是m+1号
   for(int i=1;i<=n;i++)
   {
       cin>>w[i];
       sum+=w[i]; //先把所有人的接水量都加起来    
   }
  //按接水量模拟
   while(sum!=0) //当还没有接完水的时候继续循环
   {
       for(int i=1; i<=m; i++) //枚举m个水龙头
       {
           if(w[i]>0) //在这个水龙头的人的水没接完
           {
               w[i]--; //接水量减1
               sum--;   //总量减1
           }
           if(w[i]==0) //在这个水龙头的人接水完了,下个人跟上
           {
               w[i]=w[nextt]; //下一个人接替上
               w[nextt]=0;   //重置为0
               if(nextt!=n) nextt++;   // 不到最后一个人就更新下一个人的编号
               /*
               上面两行代码要一块分析,假如最后三个水龙头的水量分别是 5,4,3
               当三秒过后,3号水龙头接完,此时出现w[i]=0, 此时已经没有人可以替换了,
               因为人都用完了,next值不会加1,那么w[i]还是保留最后一个人的接水量,
               然后就死循环了,所以这个地方首先就是将 w[next]清空,防止出现死循环的
               现象。
               */
           }    
       }
       t++; //累计时间
   }
    cout<<t;
    return 0;
}

【思路2】

因为每次被替换下来的一定是当前在水龙头队列里接水的最小一个或几个人,那么我们把找出最小的,把他替换掉。

#include<cstdio>
int n,m,ans,w[105];//注意 不要以为n是水龙头的个数
int main() {
   scanf("%d%d",&n,&m);
   for(int i=0; i<m; i++) {
       scanf("%d",&w[i]);
       if(ans<w[i]) ans=w[i]; //找到最小值
   }
   int minn,step,tmp;
   for(int i=m; i<n; i++) {
       minn=1e9;
       for(int i=0; i<m; i++)
           if(minn>w[i]) {
               minn=w[i]; //找到最小值
               step=i;     //记录位置
           }
       scanf("%d",&tmp);   //将下一个同学补上
       w[step]+=tmp;
       if(ans<w[step]) ans=w[step]; //更新答案
   }
   printf("%d\n",ans);
   return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

NOIP2011年普及组T2 统计单词数

【题目描述】一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给...

NOIP2016年普及组 T2 回文日期

【题目描述】日常生活中,通过年、月、日这三个要素可以表示出一个唯一确定的日期。牛牛习惯用8位数字表示一个日期,其中,前4位代表年份,接下来2位代表月份,最后2位代表日期。显然:一个日期只有一种表示方法...

NOIP/CSP考试中需要注意的一些问题(持续更新)

1.gets问题考试中请不要使用gets函数读取字符数组。可以用cin的方式读取。如果是字符串,请直接使用string及getline的方式读取。2.strlen问题在考试中,如果使用strlen函数...

NOIP2003年普及组 T1 乒乓球

【题目描述】国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革,以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议,有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位,他退...

NOIP2008年普及组T1 ISBN号

【题目描述】每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括9位数字、1位识别码和3位分隔符,其规定格式如“x-xxx-xxxxx-x”,其中符号“-”是分隔符(键盘上的减号),最后一...

NOIP2014年普及组T1 珠心算测验

【题目描述】珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。某学校的珠心算老师采用一种快速考察珠心算加...