//WA了……

#include "cstdio"
#include "memory"

const int maxn=25;
bool I//判断是否加空行;
int a,//最多鱼数
    s,//贪心中的鱼数
    k,//钓鱼次数
    h,n,t[maxn+1],f[maxn+1],d[maxn+1],
    T[maxn+1],//当前每个湖的鱼的数量
    B[maxn+1],//最优解的每个湖钓鱼次数
    H[maxn+1],//堆
    S[maxn+1];//当前解的每个湖的钓鱼次数

int main(void)
{
  bool Init(void);
  void Greedy(void);
  void Print(void);
  for(I=false;;I=true)
  {
    if(Init()) return 0;
    if(I) putchar('\n');
    Greedy();
    Print();
  }
}

bool Init(void)
{
  int i;
  scanf("%d",&n);
  if(n==0) return true;
  scanf("%d",&h);
  h*=60;//换算成minites
  for(i=1;i<=n;i++) scanf("%d",&f[i]);
  for(i=1;i<=n;i++) scanf("%d",&d[i]);
  for(i=1;i<n;i++) scanf("%d",&t[i]);
  a=0;
  memset(B,0,sizeof(B));
  return false;
}

void Greedy(void)
{
  int i,j,l;//l记录当前在哪个湖钓鱼
  void BuildHeap();//建堆
  int Max(int&);//取最大值
  void UpdateAnswer();//更新解
  for(k=1;k<=n;k++)
  {
    h-=5*t[k-1];//计算还剩多少时间
    if(h<=0) break;
    i=h/5;//i记录可以钓多少次鱼
    s=0;
    memset(S,0,sizeof(S));
    BuildHeap();
    for(j=0;j<i;j++)
    {
      s+=Max(l);
      S[l]++;
    }
    if(a<s) UpdateAnswer();
  }
}

void Print(void)
{
  for(int i=1;i<n;i++) printf("%d, ",5*B[i]);
  printf("%d\nNumber of fish expected: %d\n",5*B[n],a);
}

void swap(int&,int&);

void BuildHeap()
{
  int i;
  for(i=1;i<=k;i++) H[i]=i,T[i]=f[i];
  for(i=k;i>1;i--)
    if(T[H[i]]>T[H[i>>1]]) swap(H[i],H[i>>1]);
}

int Max(int &l)
{
  int i,M;
  if(T[H[1]]<=0)
  {
    l=1;
    return 0;
  }
  M=T[i=l=H[1]];//取最优解
  T[l]-=d[l];//更新
  i=1;
  while((((i<<1)<=k)&&(T[H[i<<1]]>T[H[i]]))||
        ((((i<<1)+1)<=k)&&(T[H[(i<<1)+1]]>T[H[i]])))
    if((((i<<1)+1)>k)||(T[H[i<<1]]>T[H[(i<<1)+1]])) swap(H[i],H[i<<1]),i<<=1;
    else swap(H[i],H[(i<<1)+1]),i=(i<<1)+1;
    //维护堆
  return M;
}

void UpdateAnswer()
{
  a=s;
  for(int i=1;i<=k;i++) B[i]=S[i];
}

void swap(int &i, int &j)
{
  int t;
  t=i;
  i=j;
  j=t;
}

• UP…… (0) Exile_oi 2006-05-04 19:42:07