[2010年NOIP普及组] 接水问题

[2010年NOIP普及组] 接水问题

• 分析：根据题意，要输出所用时间最长的那个人（包括那个人在等待的时间），分为两种情况，第一种是水龙头多于要打水的人数，这种情况下就可以直接写一个比较函数输出最大的人打水所用的时间，另一种是水龙头少于要打水的人，这种情况就要写一个函数比较哪个打水的人用的时间最少，下一个没排上的人就接在用的时间最少的那个人后面，以此类推，最后再次调用函数比较谁用的时间最长，然后输出所用的最长时间。

• #include<iostream>
  #include<cstdio>
  #include<algorithm>
  using namespace std;
  int a[10001],b[1000001];//a水龙头数 b人数
  int findmax(int *a,int x,int y)//指针指向数组a
  {
  int k,max=0;
  for(int i=x;i<=y;i++)
  if(max<a[i])//每个人都有水龙头
  {//找用时最长的那个就行
  max=a[i];
  k=i;//确定位置 方便被调用
  }
  return k;
  }
  int findmin(int *a,int x,int y)
  {
  int k,min=999999;
  for(int i=x;i<=y;i++)
  if(min>a[i])//找已在的用时最短的
  {
  min=a[i];
  k=i;//确定位置 方便被调用
  }
  return k;
  }
  int main()
  {
  int n,m,i,j;
  cin>>n>>m;
  for(i=1;i<=n;i++)
  cin>>b[i];
  if(n<=m)//水龙头数多
  {
  j=findmax(b,1,n);
  cout<<b[j]<<endl;
  }
  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);//再在全部完成后找用时最长的
  cout<<a[j]<<endl;
  }
  return 0;
  }