NOIP 2010 普及组 复赛 water 接水问题
1.一开始想的是队列,但觉得比较复杂。
2.稍微想了想,接完水,马上加上下一个接水的,也就是在最少耗时的水龙头上加上下一位。找最小值
3.最终找到最长时间的水龙头,即耗时。找最大值
//洛谷 P1190 接水问题
//难度:入门难度
//考点:输入,输出 ,找最大值,找最小值,函数的写法
//适用:小学生
附上AC代码,编译环境Dev-C++4.9.9.2
#include <stdio.h>
int a[100+10];//水龙头数
int b[10000+10];//人数
int findmax(int *a,int b,int e){
int i;
int max=0;
int k;
for(i=b;i<=e;i++)
if(max<a[i]){
max=a[i];
k=i;
}
return k;
}
int findmin(int *a,int b,int e){
int i;
int min=999999;
int k;
for(i=b;i<=e;i++)
if(min>a[i]){
min=a[i];
k=i;
}
return k;
}
int main(){
int i,j;
int n,m;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
if(n<=m){//水龙头数多
j=findmax(b,1,n);
printf("%d\n",b[j]);
}else{//人数多
for(i=1;i<=m;i++)
a[i]=b[i];
for(i=m+1;i<=n;i++){//加入后续打水学生
j=findmin(a,1,m);
a[j]+=b[i];
}
j=findmax(a,1,m);
printf("%d\n",a[j]);
}
return 0;
}
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。