题解：P1190 [NOIP2010 普及组] 接水问题

mairuisheng · 2025-01-07 13:00:37 · 题解

P1190 [NOIP2010 普及组] 接水问题

主要算法：贪心

分析：想要得到最优的接水方案，就要使每个水龙头接水量的最大值最小，因为他们的初始接水顺序已经确定，所以每次把当前同学的接水量加到目前接水量最小的水龙头上，最后统计所有水龙头中最大的接水量作为答案。

#include<cstdio>
#include<cmath>
using namespace std;
inline int read()
{
    char s;
    int x=0;
    s=getchar();
    while(s>='0'&&s<='9')
    {
        x=x*10+(s-48);
        s=getchar();
    }
    return x;
}
int max(int x,int y)
{
    return x>y?x:y;
}
int n,m,ans;
int p[101];//水龙头接水量
int main()
{
    int i,j,minn,k,x;
    n=read();
    m=read();
    for(i=1;i<=n;++i)
    {
        x=read();
        minn=2147483646;//设为一个较大值，方便比较
        for(j=1;j<=m;++j)
        {
            if(p[j]<minn)//找到比目前接水量小的水龙头
            {
                minn=p[j];
                k=j;//保存编号
            }
        }
        p[k]+=x;//将这位同学分配到第k个水龙头
    }
    for(i=1;i<=m;++i)ans=max(ans,p[i]);//取最大值
    printf("%d",ans);
    return 0;
}