天天看点

NOIP 2010 普及组 复赛 water 接水问题

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;

}